1 Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики Исчисление высказываний Высказывание – утверждение о математических объектах, которому можно однозначно приписать истинностное значение – ИСТИНА или ЛОЖЬ. Обозначения:ИСТИНА,Т,И,1 ЛОЖЬ, F, Л, 0. Рассматриваем следующие операции над этими двумя значениями:,,,, Операции можно задать с помощью следующих таблиц (таблицы истинности) ab a b a ЛЛЛЛИИИ ЛИЛИИЛ ИЛЛИЛЛЛ ИИИИИИ Легко проверить, что множество { И, Л } образует решетку относительно операций и, при этом, если рассмотреть операцию в качестве операции дополнения, то эта решетка представляет собой Булеву алгебру с 0 = Л и 1 = И.

2 Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики Формулы исчисления высказываний Рассмотрим понятие переменной – a, b, c,… x, y,… Будем строить формулы, последовательно вводя операции над константами И и Л и переменными: Атомарная формулаx, И, Л Отрицание( F ), где F - формула Конъюнкция( F 1 F 2 ), где F 1, F 2 - формулы Дизъюнкция( F 1 F 2 ), где F 1, F 2 - формулы Следование( F 1 F 2 ), где F 1, F 2 - формулы Эквивалентность( F 1 F 2 ), где F 1, F 2 - формулы Учитывая приоритеты операций и их ассоциативность (слева направо), будем опускать «лишние» скобки. Примеры формул исчисления высказываний: 1. a a 2. (a b) (a b) 3. a a 4. a b a b Для заданной формулы F обозначим Var(F) множество входящих в формулу переменных. Интерпретация формулы – функция на Var(F) I : Var(F) { И, Л } Если задана интерпретация, то можно вычислить значение формулы Val(F, I ) { И, Л } Тавтология – формула, истинная в любой интерпретации: Val(F, I ) = И для любой I Противоречие – формула, ложная в любой интерпретации: Val(F, I ) = Л для любой I (1), (4) – примеры тавтологий; (3) – противоречие; (2) – ни тавтология, ни противоречие

3 Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики Логическое следствие и эквивалентность формул Говорят, что формула B является логическим следствием формулы A (запись: A B), если в любой интерпретации, в которой истинна формула A, формула B также истинна. Например: a a b a b Говорят, что формулы A и B эквивалентны, если A B и B A (запись: A B ). Можно еще сказать, что две формулы эквивалентны, если они в любой интерпретации одновременно истинны или одновременно ложны. Например: a a a b a b Три теоремы: Теорема 1 (связь между логическим следствием и операцией логического следования): A B тогда и только тогда, когда формула A B – тавтология. Теорема 2 (связь между эквивалентностью формул и операцией логической эквивалентности): A B тогда и только тогда, когда формула A B – тавтология. Теорема 3 (о подстановке): если в некоторой формуле подставить вместо некоторой подформулы эквивалентную ей подформулу, то получившаяся формула будет эквивалентна исходной. Доказательство всех трех теорем очевидно.

4 Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики. Эквивалентное преобразование формул Несколько важных эквивалентностей исчисления высказываний законы булевой алгебры: 1.a a a,a a a 2.a b b a,a b b a 3.(a b) c a (b c),(a b) c a (b c) 4.(a b) a a,(a b) a a 5.a (b с) (a b) (b c),a (b c) (a b) (a c) 6.Л a Л,И a И 7.a a Л,a a И идемпотентность коммутативность ассоциативность поглощение дистрибутивность ограниченность 8. a a 9. (a b) a b инволютивность законы де Моргана исключение «третьего» (a b) a b исключение операций, не являющихся операциями решетки: 10.a b a b 11.a b (a b) ( a b)

5 Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики Представление логических функций в стандартных формах Логическая функция – это функция логических переменных и логическим результатом. f : B B … B B, где B = { И, Л } Логическую функцию можно задавать с помощью формул исчисления высказываний, например: f(a, b, c) = (a b) c Верно ли, что любую логическую функцию можно задать с помощью формулы? Определение: формула вида a 1 a 2 … a k, где каждый a i – это переменная или ее отрицание, называется дизъюнктивным термом. Формула, представляющая собой дизъюнкцию дизъюнктивных термов, называется формулой в дизъюнктивной нормальной форме (ДНФ). Например, следующие формулы находятся в ДНФ: (a b) ( a b) a a b c b Следующие формулы не находятся в ДНФ: a ( b a) (a b) c Если в каждом дизъюнктивном терме ДНФ содержатся все переменные формулы, то такая ДНФ называется совершенной (СДНФ). Дизъюнктивная нормальная форма: содержит только операции,, всегда может быть записана без скобок

6 Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики. Представление логических функций в стандартных формах Теорема: любая логическая функция может быть представлена в виде формулы в СДНФ. Пусть функция f зависит от k переменных a 1, a 2, … a k. Выберем те наборы значений, на которых функция принимает значение И и для каждого такого набора запишем дизъюнктивный терм, содержащий все переменные a 1, a 2, … a k, причем если в наборе значение переменной есть И, то в дизъюнктивный терм включаем саму эту переменную, а если значение Л, - то ее отрицание. Формула, составленная из этих дизъюнктивных термов и есть искомая формула в СДНФ. Пример: зададим функцию трех переменных в табличном виде abcf (a, b, c) ЛЛЛИ ЛЛИЛ ЛИЛЛ ЛИИИ ИЛЛЛ ИЛИЛ ИИЛИ ИИИЛ a b c f (a, b, c) = ( a b c) ( a b c) (a b c) Замечание: всего логических функций k переменных возможно 2 2 k

7 Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики Полные системы логических операций Определение: набор логических операций называется полной системой операций, если любую логическую функцию можно представить в виде формулы, содержащей только переменные и операции из этого набора. Например, набор операций,, является полной системой операций. Докажем, что набор операций, также является полной системой операций. a b a b ( a b) (a b) Существует ли полная система операций, состоящая из единственной логической операции? aba | b a b ЛЛИИ ЛИИЛ ИЛИЛ ИИЛЛ | - штрих Шеффера - стрелка Пирса Каждая из этих двух операций представляют собой полную систему операций. Доказательство: a a | a a a a b a | b ( a b) Упражнение: выразить операции и через штрих Шеффера и стрелку Пирса.