Слайд 1Тема 5. Элементы математической логики
Слайд 25.1 Алгебра высказываний
Высказывание – некоторое утверждение, относительно которого нас интересует
только его истинность или ложность.
Высказывание называют простым (элементарным), если его
истинность не зависит от истинности других высказываний.
Высказывание называют сложным (составным), если оно зависит от истинности других высказываний.
Слайд 3 В алгебре высказываний объектом исследования является множество высказываний,
а операциями – некоторые логические операции, каждую из которых можно
рассматривать как некоторое сложное высказывание.
Определяются эти операции следующими таблицами истинности. Например, операции «дизъюнкция» соответствует сложное высказывание, которое ложно тогда и только тогда, когда A ложно и B ложно
Слайд 4В дальнейшем каждое простое высказывание можно связать с некоторой двоичной
переменной.
Слайд 5Поэтому сложное высказывание можно связать с некоторой двоичной (логической) функцией.
Используя
подобную связь можно сказать, что алгебра высказываний есть одна из
интерпретаций алгебры логических функций.
Любое сложное высказывание можно представить в виде некоторой формулы. Дадим определение формулы:
Каждый символ a, b, c… есть формула;
Если А и В – формулы, то формулами являются А*В, А\/В, где * - любая операция из других формул нет.
Слайд 6 Для установления порядка выполнения операций в формулах используются
скобки. При их отсутствии порядок устанавливается приоритетом операций.
Формула
истинна или ложна в зависимости от того, истинно или ложно соответствующее ей высказывание.
Слайд 7 Формула может быть истинной при одном наборе значений
переменных и ложным при другом наборе. Формула, которая является истинной
хотя бы при одном наборе значений переменных, называется выполнимой. Формула ложная при всех наборах значений переменных называется противоречием (тождественно ложной). Формула, истинная при всех наборах значений переменных называется тавтологией (тождественно истинной).
Слайд 8Для каждой формулы алгебры высказываний можно найти множества КНФ и
ДНФ.
Для этого нужно:
Заменить все логические операции булевыми операциями. Это можно
сделать используя следующие равносильные формулы.
Заменить знак отрицания относящийся ко всему выражению на знаки относящиеся к отдельным переменным
Слайд 9Избавиться от знаков двойного отрицания
Применить, если нужно, закон дистрибу-тивности и
формулы поглощения.
AvAВ = A,
A(AС) = A
Теорема 1: формула алгебры высказываний является тождественно истинной , когда каждый множитель её КНФ содержит пару слагаемых, одно из которых является элементарным высказыванием, а другое его отрицанием.
Слайд 10Теорема 2: формула алгебры высказываний является тождественно ложной , когда
каждый множитель её ДНФ содержит пару сомножителей, один из которых
является элементарным высказыванием, а другое его отрицанием.
Данные теоремы позволяют решить вопрос о выполнимости любой формулы алгебры высказываний.
Слайд 11Между формулами можно установить отношение формально импликации (==>). Формулы А
и В находятся в отношении формальной импликации, точнее А имплицируем
В (А==>В), если формула В истинна на всех наборах переменных, на которых истинна формула А. В таких случаях говорим, что формула В логически следует из формулы А.
Формулы А и В равносильны (логически эквивалентны) (А<=>В) если любая из них следует из другой. Очевидно, что таблица истинности равносильных формул совпадают.
Слайд 12Основные тавтологии алгебры высказываний
1.Закон тождествия:
2. Закон противоречия:
3. Закон исключения третьего:
4.
Закон двойного отрицания:
5. Закон «истинно из чего угодно»:
6. Закон
«из ложного что угодно»:
7. Закон modus ponens:
8.Закон modus tollens:
9. Закон силлогизма:
