Буквы, обозначающие высказывания (А,В,…) можно рассматривать как имена логических переменных, так как ими можно заменить любые высказывания (с любым содержанием). То есть, построенные нами таблицы истинности, задающие логические операции, верны для любых высказываний.
Говоря о логических операциях над высказываниями, мы фактически рассмотрели логические операции над двумя логическими переменными.
В алгебре логики из логических переменных, логических констант (0 и 1) и знаков логических операций составляются логические выражения (подобно тому, как в алгебре чисел формируются арифметические выражения).
Выражения алгебры логики называются формулами.
Логические переменные принимают два значения: 0 и 1 («истина» и «ложь»).
Можно определить и логические функции от логических переменных.
Например, F(A, B)=AÚB – логическая функция двух переменных – А и В.
Две переменные, каждая из которых может быть либо нулём, либо единицей, образуют 22=4 различных набора значений: (0,0), (0,1), (1, 0), (1, 1). На каждом наборе функция принимает значение либо 0, либо 1. Например, некоторая функция двух переменных будет полностью определена так: F(0, 0)=1, F(0, 1)=1, F(1, 0)=0, F(1,1)=0. Так каждая функция двух переменных однозначно задаётся четырьмя значениями, каждое из которых равно либо 0, либо 1, то количество таких функций будет равно количеству комбинаций этих четырёх значений. Таких комбинаций 24=16. То есть всего существует 16 различных функций двух переменных.
Функцию можно задать в табличном виде и в виде формулы.
Итак, формулы алгебры логики (пропозициональные формулы) – формулы, построенные из знаков переменных и знаков функциональных операций с соблюдением определённых правил построения формул.
Таблицу, показывающую, какие значения принимает сложное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний, называют таблицей истинности сложного высказывания.
Операции одного приоритета выполняются слева направо. Для изменения порядка действий используют скобки.
1. Подсчитать количество переменных в формуле.
2. Вычислить количество строк в таблице по формуле m=2n.
3. Подсчитать количество логических операций в формуле.
4. Установить последовательность выполнения логических операций с учётом скобок и приоритетов.
5. Определить количество столбцов таблицы истинности. Количество столбцов равно сумме количества переменных и количества операций, входящих в сложное высказывание.
6. Выписать наборы входных переменных с учётом того, что они представляют собой натуральный ряд n-разрядных двоичных чисел от 0 до 2n-1.
7. Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в п.4 последовательностью.
Если сложное высказывание истинно при всех значениях входящих в него переменных, то такое высказывание называется тождественно истинным или тавтологией (обозначается константой 1).
Если сложное высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется тождественно ложным (обозначается константой 0).
Если значения сложных высказываний совпадают на всех возможных наборах значений входящих в них переменных, то такие высказывания называются равносильными, тождественными, эквивалентными.
Пример 1.7. Построить таблицу истинности для формулы .
Решение.
1. Количество переменных n=3.
2. Количество строк в таблице m=2n=23=8.
3. Количество операций: 5.
4. Количество столбцов: 3+5=8.
5. Составим таблицу истинности с учётом порядка операций.
А
В
С
1. Что такое логика?
2. Назовите этапы развития логики.
3. Что является предметом математической логики?
4. Всякое ли утверждение называется высказыванием? Приведите примеры истинных высказываний, ложных высказываний, предложений не являющихся высказываниями, простых высказываний, сложных высказываний, тождественно истинных высказываний, тождественно ложных высказываний. Ответ обоснуйте.
5. Какие операции можно выполнять над высказываниями?
6. Как образуется инверсия? Приведите примеры.
7. Как образуется конъюнкция? Приведите примеры.
8. Как образуется дизъюнкция? Приведите примеры.
9. Как образуется импликация? Приведите примеры.
10. Как образуется эквивалентность? Приведите примеры.
11. Дайте определение штриха Шеффера.
12. Дайте определение стрелки Пирса.
13. Дайте определение кольцевой суммы.
14. Определите, какие из следующих пар высказываний являются эквивалентными, а какие нет:
a.
b. ;
c. ;
15. Составьте таблицы истинности формул. Установить, являются ли они тождественно истинными, тождественно ложными.
Тема 2. Законы логики
При решении логических задач часто приходится упрощать формулы. Упрощение формул в булевой алгебре производится на основе эквивалентных преобразований, опирающихся на основные логические законы.
Среди законов особо выделяются такие, которые содержат одну переменную.
Закон тождества: А=А.
Всякая мысль тождественна самой себе.
Закон тождества означает, что в процессе рассуждения нельзя подменять одну мысль другой, одно понятие другим. При нарушении этого закона возможны логические ошибки.
Закон непротиворечия: или .
Не могут быть одновременно истинными суждение и его отрицание.
Закон исключённого третьего: .
В один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано.
Закон исключённого третьего не является законом, признаваемым всеми логиками в качестве универсального закона логики. Этот закон применяется там, где познание имеет дело с жёсткой ситуацией: «либо-либо», «истина-ложь». Там же где встречается неопределённость (например, в рассуждениях о будущем), закон исключённого третьего часто не может быть применён.
Рассмотрим высказывание: Это предложение ложно.
Оно не может быть истинным, потому, что в нём утверждается, что оно ложно. Но оно не может быть и ложным, потому, что тогда оно было бы истинным. Это высказывание не истинно и не ложно, а потому нарушается закон исключённого третьего.
Парадокс (греч. paradoxos – неожиданный, странный) в этом примере возникает из-за того, что предложение ссылается на само себя.
Другим известным парадоксом является задача о парикмахере:
В одном городе парикмахер стрижёт волосы всем жителям, кроме тех, кто стрижёт себя сам. Кто стрижёт волосы парикмахеру?
В логике из-за её формальности нет возможности получить форму такого ссылающегося на само себя высказывания. Это ещё раз подтверждает мысль о том, что с помощью логики нельзя выразить все возможные мысли и доводы.
Закон двойного отрицания: .
Если отрицать дважды некоторое высказывание, то в результате получиться исходное высказывание.
Свойства констант:
Законы идемпотентности:
Сколько бы раз мы не повторяли данное высказывание, его значение не изменится.
Законы коммутативности:
Законы ассоциативности:
Законы дистрибутивности:
Законы поглощения:
Законы де Моргана:
Правило замены операции импликации:
Правила замены операции эквивалентности:
Минимизация (упрощение) ФАЛ – это замена высказываний на равносильные на основе законов алгебры высказываний с целью получения высказываний более простой формы.
