Программа по формированию навыков безопасного поведения на дорогах и улицах «Добрая дорога детства» 2
Скачать 1.97 Mb.
|
различны все члены дизъюнкции;различны все члены каждой конъюнкции; ни одна конъюнкция не содержит одновременно переменную и отрицание этой переменной; каждая конъюнкция содержит все переменные, входящие в формулу, т.е. имеет вид  ,где дизъюнкция берется по всем наборам с=(с1, с2, …, сn) из 0 и 1, для которых F(c)=1. Теорема (о СДНФ). Для всякой не равной тождественному нулю формулы логики высказываний F(x1, x2, …, xn) существует такая формула F1, зависящая от того же списка переменных и находящаяся в СДНФ относительно этого списка, что F1 выражает собой формулу F. Формула F1 определена однозначно с точностью до перестановки дизъюнктивных членов. Опишем два способа приведения к совершенным нормальным формам. 1-й способ – аналитический. Приведение к СДНФ. Алгоритм приведения.
Полученная формула и является СДНФ данной формулы. Привести следующие формулы к СДНФ с помощью равносильных преобразований: 1. ;2. ;3. .Решение. 1. .2. 3. 2-й способ – табличный. Составляем таблицу истинности для данной функции. Строим таблицу значений формулы. Рассматриваем только те строки, в которых значение формулы равно единице. Каждой такой строке соответствует конъюнкция всех аргументов (без повторений). Причем, аргумент, принимающий значение 0, входит в нее с отрицанием, значение 1 – без отрицания. Наконец, образуем дизъюнкцию всех полученных конъюнкций. Построить СДНФ для данных формул логики высказываний. 1. .2. Решение. 1. .Строим таблицу истинности для формулы F: №xyz 00001101001110201000030110104100111510111161100007111011Рассматриваем только 4, 5 и 7 наборы, так как только на этих наборах формула принимает значение равное единице.СДНФ имеет вид: 2. Строим таблицу истинности для формулы F: №xyx yF=(x y)xy00010101102100031111СДНФ (1): № 3: F = x y Тема 2.4 Конъюнктивная нормальная форма. Высказывательная форма, состоящая из переменных или отрицательных переменных, применением только одной операции конъюнкции, называется элементарной конъюнкцией. Высказывательная форма, состоящая из элементарных дизъюнкций, применением только одной операции конъюнкции называется конъюнктивной нормальной формой (КНФ). Теорема: Для любой высказывательной формы существуют равносильные ДНФ и КНФ. Доказательство:
Способы построения ДНФ и КНФ для любой высказывательной формы:
для получения КНФ к Ы* применяется второй дистрибутивный закон: Совершенной конъюнктивной формулой формулы алгебры высказываний (СКНФ) называется КНФ, в которой:
,где конъюнкция берется по всем наборам с=(с1, с2, …, сn) из 0 и 1, для которых F(c)=0. Теорема (о СКНФ). Для всякой не равной тождественной единице формулы логики высказываний F(x1, x2, …, xn) существует такая формула F1, зависящая от того же списка переменных и находящаяся в СКНФ относительно этого списка, что F1 выражает собой формулу F. Формула F1 определена однозначно с точностью до перестановки конъюнктивных членов. Опишем два способа приведения к совершенным нормальным формам. 1-й способ – аналитический Приведение к СКНФ. Алгоритм приведения.
Полученная формула и является СКНФ данной формулы. Привести следующие формулы к СКНФ с помощью равносильных преобразований: 1. ;2. .Решение. 1. 2. 2-й способ – табличный. Составляем таблицу истинности для данной функции. Рассматриваем только те строки таблицы, где формула принимает значение 0. Каждой такой строке соответствует дизъюнкция всех переменных (без повторений). Причем аргумент, принимающий значение 0, берется без отрицания, значение 1 – с отрицанием. Наконец, образуют конъюнкцию полученных дизъюнкций. Построить СКНФ для данных формул логики высказываний. 1. .2. Решение.
№xyz 0000010010201003011041001510116110071111Рассматриваем только наборы, на которых формула принимает значение ноль.СКНФ (0): № 0, 1, 2, 3, 6:
№xyF=(x y)xy0000101021003111СКНФ (0): № 0, 1, 2: Тема 2.5 Равносильные формулы. Свойства. Два высказывания называются равносильными, если равны их истинностные функции, рассматриваемые как функции от всех значений переменных, т.е. на каждом наборе значений оба высказывания принимают одинаковые значения. Основы равносильности: 1. Коммутативность. а) (для конъюнкции);б) (для дизъюнкции).2. Ассоциативность. а) (для конъюнкции);б) (для дизъюнкции).3. Дистрибутивность. а) (для конъюнкции относительно дизъюнкции);б) (для дизъюнкции относительно конъюнкции).4. Закон де Моргана. а) ┐ ┐┐ (отрицание конъюнкции есть дизъюнкция отрицаний);б) ┐ ┐┐ (отрицание дизъюнкции есть конъюнкция отрицаний).5. Идемпотентность. а) (для конъюнкции);б) (для дизъюнкции).6. Поглощение. .┐7. Расщепление (склеивание). а) (1–ый закон расщепления); б) (2–ой закон расщепления).8. Двойное отрицание. ┐┐х=х 9. Свойства констант. а) б) в) г) д) е) .10. Закон противоречия. 11. Закон “исключенного третьего”. Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа “ ”. Докажем, например, равносильность 4а. Для этого составим таблицу.Таблица ху 00 1 10 1 0 10 0 0 11 1 1 01 1 0 01 0 1 01 1 1 0 Из таблицы видно, что , что и требовалось доказать.Тест 1. Следующее высказывание может быть интерпретировано как сложное высказывание: "Неверно, что первым пришел Петр или Павел". Каковы составляющие его элементарные высказывания? а) А: "Неверно, что первым пришел Петр"; В: "Неверно, что первым пришел Павел"; б) А: "Первым пришел Петр"; В: "Неверно, что первым пришел Павел"; в) А: "Первым пришел Петр"; В: "Первым пришел Павел". 2. Какой из формул может быть записано высказывание предыдущего вопроса? а) А ∨ В; б) А ∨ В; в) А ∧В. 3. Будет ли высказывание S=(А→В)∧(В→С)→(А→С): а) тождественно истинным; б) тождественно ложным; в) переменным. 4. В высказывании S: "Треугольники равны только тогда, когда равны их стороны". Равенство углов в треугольнике является: а) необходимым условием; б) достаточным условием; в) необходимым и достаточным условием. Самостоятельная работа №3. Самостоятельная работа №4. Контрольная работа I вариант
F=(x∧y∧z)∨(¬x→y) II вариант
F=(¬y→¬x)∧(x∨¬y∨¬z) Раздел 3. БУЛЕВЫ ФУНКЦИИ. Тема 3.1 Понятие булевой функции. Функция f, зависящая от n переменных x1, x2, ...., xn, называется булевой, если функция f и любой из ее аргументов Xi, (i=1..n) принимают значения только из множества {0, 1}. Аргументы булевой функции также называются булевыми. Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству {0, 1}. Основные булевы функции 1.  ;2. ;3. ;4. ;5. ;6. ;7. ;8. ;9. ;Все функции f являются одноместными: xyf1f2f3f4f5f6f7f8f911100111001101000101110110111011000101100010 Тема 3.2 Совершенная ДНФ. Совершенная КНФ. |
y; F3(x,y)=x
y
