Логика высказываний
методическая разработка по математике на тему

Урок 8.Тема: Высказывания и операции над ними. Таблицы истинности.

Понятие высказывания

Под высказыванием понимается ________________________________

____________________________________________________________________________________________________________________________________________________________________________________

Например, ____________________________________________________________

____________________________________________________________

Операции над высказываниями

Связки русского языка: не, и, или, если…тогда (значит, следовательно), тогда и только тогда (равносильно, эквивалентно)

Отрицанием (инверсией) высказывания X называется ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Конъюнкцией  X  Y двух высказываний называется высказывание,_______________________________________________

____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Дизъюнкцией X Y двух высказываний называется высказывание,________________________________________________________

____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

____________________________________________________________

Импликацией двух высказываний X  Y называется высказывание,________________________________________________

____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Эквиваленцией двух высказываний X  Y называется высказывание,____________________________________________________________________________________________________________

____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Таблицы истинности

Операнды логических операций могут принимать только два значения: __________. Поэтому каждую логическую операцию __________________________________________ легко задать с помощью таблицы, указав значение результата операции в зависимости от значений операндов.

Такая таблица называется _________________________________

________________________________________________________

Урок 9.Формулы логики высказываний. Виды ФЛВ. Равносильность ФЛВ.

Алфавит логики высказываний содержит следующие символы: две буквы _________, обозначающие логические константы «ложь» и «истина»; переменные (прописные буквы), обозначающие высказывания: А1, А2, А3 ...; символы скобок: (...),{...}; символы логических операций: _______________________________________________________________

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

Например: F=(((А&())C)()

__________________________________________________________

Чтобы формулы не были громоздкими, договоримся опускать некоторые скобки, учитывая приоритет логических операций ("силу" связок). В табл. выше логические операции записаны в порядке убывания приоритета. Учитывая эту договоренность, вышеприведенную формулу можно записать короче:

F=(А&C)

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

Виды ФЛВ.

1.Формула высказываний называется ____________________
_____________________________________________________, если при любых наборах высказывательных  переменных она принимает значение «истина» - превращается всегда в истинное (ложное) высказывание.

Естественно, что если формула Ф1(P1,..., Рk) ↔  Ф2(P1,..., Рk) является тавтологией, то формулы Ф1(P1,..., Рk) и  Ф2(P1,..., Рk) равносильны.

Например, высказывание «город находится на Земле» — тавтология, так как при подстановке любого названия города смысл этого высказывания не изменится.

Пример:_____________________________________________________

2.  Формулы, принимающие значение "истина" хотя бы при одном наборе списка высказывательных  переменных, называются ________________________________________________________________

3.  Формулы, принимающие значение "ложь" хотя бы при одном наборе списка высказывательных  переменных, называются ________________________________________________________________

Схема: Виды  формул логики высказываний.

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

Пример: Является ли тавтологией формула F = (X Y) ?

Построим таблицу истинности для формулы F (табл.).

Таблица истинности

ВЫВОД:______________________________________________________________

Урок 10: Нормальные формы формул. Проблема разрешимости.

Нормальные  формы

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

При большом числе переменных установить тип формулы удобнее с помощью так называемых нормальных форм. Для этого введем понятия:

Опр 1.Элементарной дизъюнкцией (ЭД) наз-ся дизъюнкция k высказывательных переменных или их отрицаний.(k1).

Пример 1:

Опр 2.Элементарной конъюнкцией (ЭК) наз-ся конъюнкция k высказывательных переменных или их отрицаний.(k.

Пример 2:

Опр 3. ФЛВ записана в нормальной форме, если в формуле содержатся только лишь операции  конъюнкция (, дизъюнкция () и отрицание элементарного высказывания (.

__________________________________________________________________

Опр 4. Дизъюнктивной нормальной формой (ДНФ) ФЛВ наз-ся ______________________________________________________________________

________________________________________________________________________

Опр 5. Конъюнктивной  нормальной формой (КНФ) ФЛВ наз-ся ______________________________________________________________________

________________________________________________________________________

Пример 3: определить, вид  НФ:

                                                           .          
                                                             _    .

Т1: Любую  ФЛВ можно привести равносильными преобразованиями к нормальной форме! Причем для каждой формулы можно найти множество ДНФ и КНФ!

Алгоритм построения ДНФ (КНФ):

1)_______________________________________________________________________

2) ______________________________________________________________________

3) _____________________________________________________________________

Пример 4:  Дана ФЛВ : . Найти ДНФ (дополнительно: КНФ).

Пример 5: Дана формула . (Рассмотреть самостоятельно)

Построим КНФ для этой формулы. Избавимся от знаков импликации:

Так как  и учитывая предыдущие преобразования, получаем формулу

 Избавимся от знака двойной импликации:

Применим закон де Моргана:

Получаем    

Избавимся от двойных отрицаний  и   в формуле S. Учитывая закон ассоциативности операции дизъюнкции,  внутренние скобки опускаем:

Применив формулу поглощения:

получили КНФ для исходной формулы.

Ответ:

Среди многочисленных ДНФ и КНФ существует единственная нормальная форма, для которой выполняются   свойства совершенства:

Т.О.: каждой не тождественно ложной (истинной) ФЛВ соответствует единственная совершенная форма указанного типа. Такая ДНФ (или КНФ) называется совершенной нормальной формой. Обозначаются совершенные нормальные формы как СДНФ и СКНФ.

Т2: Тождественно истинная ФЛВ имеет только СДНФ, _________________________________________________________________

Т3: Тождественно ложная ФЛВ имеет только СКНФ, _________________________________________________________________

Способы получения совершенных нормальных форм:

I способ:__________________________________________________________

II способ:________________________________________________________

Алгоритм нахождения СДНФ с помощью таблицы истинности:

________________________________________________________________________

________________________________________________________________________

________________________________________________________________________

________________________________________________________________________

Алгоритм нахождения СКНФ с помощью таблицы истинности:

________________________________________________________________________

________________________________________________________________________

________________________________________________________________________

________________________________________________________________________

Пример 7:      

 Найти совершенные (СДНФ и СКНФ) формы формулы, соответствующей функции: F(M,N,K)=F(1,0,1)=F(1,1,0)=F(1,0,0)=F(0,0,1)=1. (Дополнительно: упростите найденную формулу)

Решение: составим для данной функции таблицу истинности:

Найдем СДНФ:  

СКНФ:  

Другой способ получения совершенных нормальных форм основан на равносильных преобразованиях формулы.

Алгоритм нахождения СДНФ с помощью равносильных преобразований:

________________________________________________________________________

________________________________________________________________________

_________________________________________________________________________________________________________________________________________

Алгоритм нахождения СКНФ с помощью равносильных преобразований:

________________________________________________________________________

________________________________________________________________________

_________________________________________________________________________________________________________________________________________

Проблема разрешимости для логики высказываний.

Проблемой разрешимости для логики высказываний называют следующую проблему: существует ли алгоритм, который позволил бы для любой ФЛВ в конечное число шагов определить, является ли она тавтологией?

Данная проблема разрешима?

Т4:  ФЛВ является тавтологией т.и т.т., когда в ее КНФ, в любую из ЭД входит переменная или ее отрицание!

Практические задания:

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

1. S1: Х неверно сделал расчет или если Y считал задачу правильно, то и Z сделал это без ошибок.

S2: Если Х правильно просчитал задачу, то либо Y ошибся, либо Z сделал ее верно.

S3: Либо Х неверно просчитал задачу, либо Y решил ее верно в том и только в том случае, если Z решил ее верно.

2. S1: "Если задача сложна, но понятна, то она интересна".

S2: "Эта задача интересна, сложна, но непонятна".

S3: "Если задача сложна или непонятна, то она неинтересна".

1. Установить вид ФЛВ:

2. .  Проверить, используя равносильные преобразования, какие из следующих формул тождественно истинны:

3. Найти СДНФ и СКНФ формул, соответствующих следующей функции:

1. F(A,B,C)=  F(1,1,1)=F(1,1,0)=F(1,0,1)=F(0,0,1)=1
2. F(X,Y,Z)=F(1,0,0)=F(0,1,0)=F(0,0,1)=1
3. F(X,Y,Z)=  F(1,1,1)=F(1,0,0)=F(0,1,1)=F(0,0,0)=0

4. Найти совершенные формы ФЛВ, при помощи равносильных преобразований:

Урок 13. Двойственность. Закон двойственности в алгебре логики.

Опр 1. ФЛВ   Ф* (x,y) называется двойственной по отношению к ФЛВ Ф(x,y),  если

.

Опр 2. ФЛВ  называется самодвойственной, если ____________________________

_______________________________________________________________________

Теорема1 (принцип двойственности):  если , то  

Двойственные операции:

Пример 1.  Найти для ФЛВ  двойственную ей и отрицание. Упростить найденные ФЛВ.

Урок 14. Логические рассуждения.