Исторические факты развития вычислительной математики и техники.

МЕТОДЫ И МОДЕЛИ ОЦЕНКИ КОЛИЧЕСТВА ИНФОРМАЦИИ

СИСТЕМЫ СЧИСЛЕНИЯ

ЧИСЛОВАЯ СИСТЕМА ЭВМ

ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ

Программное обеспечение

Моделирование

АЛГОРИТМИЗАЦИЯ

Программирование

Тестирование

Основные правила Web-проектирования. Приложения для проектирования Web-страниц

Язык HTML

Стилевое оформление веб-страниц при помощи каскадных таблиц стилей CSS

Основы Web-дизайна

Динамические Web-страницы.

Вебсервера. Обзор популярных вебсерверов, их различия, особенности и использование.

Сетевые утилиты

Введение в язык программирования Java

Основы баз данных

Основы работы математическими пакетами

Основы работы JavaFX

Основы моделирования

ВОШ

Олимпиадное программирование

ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА

Основные понятия алгебры логики

Логика – наука о законах и формах мышления. Математическая логика изучает любые рассуждения с помощью методов математики.

Математическая логика входит в группу фундаментальных наук, которые образуют теоретическую основу информатики.

Центральная идея математической логики восходит еще к Г.В. Лейбницу (1646-1716) и состоит в том, чтобы записывать математические утверждения в виде последовательностей символов и оперировать с ними по формальным правилам. При этом правильность рассуждений можно проверять механически, не вникая в их смысл.

Усилиями большого числа математиков и логиков второй половины XIX и первой половины XX века (Буль, Кантор, Фреге, Пеано, Рассел, Уайтхед, Цермело, Френкель, Гильберт, фон Нейман, Гёдель и другие) эта программа была в основном выполнена.

Английский математик Джордж Буль (1815-1864) впервые применил алгебраические методы для решения логических задач.

Алгебра логики – это раздел математической логики, значения всех элементов (функций и аргументов) которой определены в двух элементном множестве: 0 и 1. Алгебра логики оперирует логическими высказываниями.

Логическое высказывание, предложение – это утверждение, в отношении которого можно однозначно сказать, истинно оно или ложно. В исчислении высказываний не рассматриваются утверждения, имеющие значения, отличные от «истинно» и «ложно». Используется двузначная логика: ответ, отличный от «Да», есть «Нет». Древние философы назвали этот принцип «законом исключенного третьего».

Высказывание не может быть выражено повелительным или вопросительным предложением. Не каждое повествовательное предложение является логическим высказыванием. Высказыванием не является, например, предложение «Информатика – интересный предмет».

Примеры высказываний:

Сканер – устройство ввода в компьютер (истинно).

Дважды два – четыре (истинно).

Плоттер является устройством ввода в компьютер (ложно).

Высказывания делятся на простые и сложные (составные). Высказывание, содержащее одну простую законченную мысль, называется простым. Значение истинности простого высказывания не зависит от значений истинности каких-либо других высказываний. Сложные высказывания образуются из двух и более простых высказываний с помощью логических операций. Значение истинности сложного высказывания зависит от значений истинности других высказываний.

Простые высказывания являются логическими аргументами, а сложные – логическими функциями аргументов.

Пример. Сидорову 20 лет и он студент и не солдат.

Для образования сложных высказываний наиболее часто используются базовые логические операции, выражаемые с помощью логических связок «и», «или», «не».

В таблице приводятся обозначения, используемые для логических связок (операций) в различной литературе.

Обозначения логических связок (операций)

Наглядной иллюстрацией этих логических связок служат следующие диаграммы:

Простые высказывания обозначаются буквами латинского алфавита (A, B, C, ...).

Истинное значение обозначают единицей (1) либо символом T (True – истина), а ложное – нулем (0) либо F (False – ложь), иногда заменяют словами «да» («yes»), «нет» («no»).

Отрицание высказывания Ā является простым высказыванием. Оно истинно, когда А ложно, и ложно, когда А истинно

Таблица истинности логического отрицания

Таблица истинности – это табличное представление логической операции, в котором перечислены все возможные сочетания значений истинности входных сигналов (операндов) вместе со значением истинности выходного сигнала (результата операции) для каждого из

этих сочетаний.

Составное высказывание, образованное в результате логического умножения (конъюнкции, лат. conjunctio – соединение), истинно тогда и только тогда, когда истинны все входящие в него простые высказывания.

Таблица истинности логического умножения

Составное высказывание, образованное в результате логического сложения (дизъюнкции, лат. disjunctio – разделение) истинно тогда, когда истинно хотя бы одно из входящих в него простых высказываний.

Таблица истинности логического сложения

Последовательность выполнения операций при отсутствии скобок в сложных логических формулах определяется старшинством операций (приоритетом). Наивысший приоритет имеет отрицание, затем следует конъюнкция и, наконец, дизъюнкция.

Основные законы алгебры логики

В алгебре логики выполняются основные законы, позволяющие производить тождественные преобразования логических выражений.

Законы алгебры логики

Закон коммутативности утверждает, что можно переставлять операнды при использовании конъюнкции или дизъюнкции. Это может показаться очевидным (в обычной алгебре слагаемые и множители можно менять местами), но имеются операторы вроде арифметического минуса, для которых это неверно: A-B отлично от B-A.

Закон ассоциативности позволяет расставлять скобки произвольным образом, если в логическом выражении используются только операции логического умножения или только операции логического сложения. В таких случаях можно вообще обойтись без скобок, так как закон ассоциативности гарантирует получение одного и того же результата независимо от того, как сгруппированы предложения.

Закон дистрибутивности. В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые.

Законы де Моргана. Отрицание дизъюнкции эквивалентно конъюнкции отрицаний. Отрицание конъюнкции эквивалентно дизъюнкции отрицаний. Эти свойства иногда выражают словами: «конъюнкция двойственна дизъюнкции».

Операция переменной с её инверсией. Закон непротиворечия: Высказывание не может быть одновременно истинным и ложным. Логическое произведение высказывания и его отрицания ложно.

Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным – третьего не дано. Результат логического сложения высказывания и его отрицания всегда принимает значение «истина».

Вместе эти законы определяют булеву алгебру. Из них можно получить другие полезные законы

Законы булевой алгебры

Большинство законов существует в двух похожих формах. Принцип двойственности гласит, что любая теорема булевой алгебры остается истинной, если в ее формулировке заменить все связки И на ИЛИ, ИЛИ на И.

Импликация и эквивалентность

Любая логическая формула может быть выражена через три базовые логические операции (ранее рассмотренные), однако на практике часто используют еще две логические связки. Первая из них называется импликацией (лат. implico – тесно связаны) и служит для задания так называемых условных высказываний. В русском языке этой логической операции соответствуют фразы если ..., то ... или когда ..., тогда ...

Импликация – двухместная операция: часть формулы до импликации называют основанием условного высказывания, а часть, расположенную за ней, – следствием. В логических формулах импликация обозначается знаком →.

Операция A→B определяет логическую функцию, тождественно совпадающую с функцией А ∨ В .

Пример 1. Сложное высказывание: «Если на улице дождь, то на улице мокро». Обозначим через А простое высказывание «на улице дождь», а через В – «на улице мокро». Тогда логической формулой этого сложного высказывания будет импликация: A→B.

Пример 2. Если число Х делится на 4, то оно делится на 2. Это означает, что высказывание (Х делится на 4) → (Х делится на 2) истинно при всех Х.

Таблица истинности логической импликации

Составное высказывание, образованное с помощью операции логического следования (импликации), ложно тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод (второе высказывание).

Однако операция логического следования несколько отличается от обычного слова «следует». Если первое высказывание (предпосылка) ложно, то вне зависимости от истинности или ложности второго высказывания (вывода) составное высказывание истинно. Это можно понимать таким образом, что из неверной предпосылки может следовать что угодно.

Другой распространенной операцией является эквивалентность (равнозначность, равносильность). Ее аналог в разговорной речи – фразы, подобные словосочетанию тогда и только тогда, когда ... или если и только если ... Для ее обозначения используется символ ↔ (или = , или ~).

Эквиваленцию A↔B можно выразить через отрицание, дизъюнкцию и конъюнкцию: (А ∨ В) & ( A ∨ B).

Пример 1. Сложное высказывание: «В зачетную книжку выставляется оценка за экзамен тогда и только тогда, когда он сдан». Обозначим через А простое высказывание «В зачетную книжку выставляется оценка за экзамен», а через В – «Экзамен сдан». Тогда логическая формула сложного высказывания запишется в виде: A↔B.

Пример 2. Многоугольник является вписанным в круг, если его вершины лежат на окружности.

Таблица истинности логической эквивалентности

Составное высказывание, образованное с помощью логической операции эквивалентности, истинно тогда и только тогда, когда оба высказывания одновременно либо истинны, либо ложны.

Вне зависимости от смысла равнозначными являются как истинные, так и ложные высказывания, например,

А = (дважды два – пять);

B = (один плюс два – шесть);

А~В («А и В равнозначны»).

Рассмотренные логические операции в порядке убывания приоритетов располагаются так: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.

Как составить таблицу истинности для логической формулы?

Согласно определению таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.

Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0,0), (0,1), (1,0), (1,1).

Если формула содержит три переменные, то возможных наборов значений переменных восемь: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т. д.

Удобной формой записи при нахождении значений формулы является таблица, содержащая, кроме значений переменных и значений формулы, также и значения промежуточных формул.

Пример. Составим таблицу истинности для формулы А ∧ B∨ А∨ B∨ А

Таблица истинности для формулы А ∧ B∨ А∨ B∨ А

Из данных таблицы 18 следует, что при всех наборах значений переменных А и В формула А ∧ B∨ А∨ B∨ А принимает значение 1, т. е. является тождественно-истинной.

Если задача сформулирована на естественном языке, её необходимо формализовать, то есть записать на языке алгебры высказываний. Полученное логическое выражение необходимо упростить и проанализировать. Упрощение логического выражения состоит в преобразовании его к более простому (по числу переменных, операций или операндов; не содержащему отрицаний неэлементарных формул) эквивалентному выражению путем использования основных законов алгебры логики. Наиболее простой вид получается при сведении функции к постоянной – 1 (истина) или 0 (ложь).

Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т. п.), тогда как другие преобразования основаны на свойствах,

которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, де Моргана и др.).

Рассмотрим на примерах некоторые приемы и способы, применяемые при упрощении логических формул.

(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией).

(применяются правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами).

(к отрицаниям неэлементарных формул применяется правило де Моргана, используются законы двойного отрицания и поглощения).

(общий множитель А выносится за скобки, комбинируются слагаемые в скобках – первое с третьим и второе с четвертым, к дизъюнкции В ⋅ С + В ⋅ С применяется правило операций переменной с её инверсией).