Файл: Методические указания по выполнению контрольной работы по учебной дисциплине ен. 02 Элементы математической логики.doc
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 26.10.2023
Просмотров: 203
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Так как в последнем столбце таблицы все значения истины, следовательно, формула тождественно истина.
3. Равносильные преобразования формул логики высказываний
Пример 1: Дана формула логики высказываний:
С помощью равносильных преобразований выясните, какая эта формула, тождественно истинная, тождественно ложная или только выполнимая.
Решение:
Таким образом, доказано, что данная формула логики тождественно истинная.
Пример 2: Упростите формулу логики высказываний с помощью равносильных преобразований.
Решение:
4. Дизъюнктивная и конъюнктивная нормальные формы.
Элементарной конъюнкцией от переменных называется формула логики высказываний, которая представляет собой конъюнкцию переменных высказываний или их отрицаний.
Примеры элементарных конъюнкций: ;
Теорема 1: Элементарная конъюнкция является тождественно ложной тогда и только тогда, когда существуют переменные высказывания и в элементарной конъюнкции для некоторого i .
Дизъюнктивной нормальной формой (ДНФ)
называют формулу логики высказываний, которые представляют собой дизъюнкцию элементарных конъюнкций.
Теорема 2 (критерий ложности): ДНФ тождественно ложна тогда и только тогда, когда в каждую элементарную конъюнкцию входят элементы вида и для некоторого i.
Замечание: i для каждой элементарной конъюнкции свой
Примеры:
1. - ДНФ
2. – ДНФ
Элементарной дизъюнкцией от переменных называют формулу логики высказываний, которая представляет собой дизъюнкцию переменных высказываний или их отрицаний.
Примеры элементарных дизъюнкций: ;
Теорема 3: Элементарная дизъюнкция является
тождественно истинной тогда и только тогда, когда существуют переменные высказывания и в элементарной дизъюнкции для некоторого i .
Конъюнктивной нормальной формой (КНФ) называют такую форму логики высказываний, которая представляет собой конъюнкцию элементарных дизъюнкций.
Теорема 4 (критерий истинности): КНФ тождественно истинно тогда и только тогда, когда каждая элементарная дизъюнкция содержит набор переменных и для некоторого i.
Замечание: i для каждой элементарной дизъюнкции свой.
Примеры:
1.
- КНФ
2. – КНФ
Две операции конъюнкция и дизъюнкция называются двойственными друг к другу, то есть конъюнкцию можно заменить дизъюнкцией, и наоборот.
Для того чтобы от дизъюнкции перейти к конъюнкции, и наоборот, нужно установить двойное отрицание и одно из них применить вместе с законом де Моргана.
Для того чтобы от ДНФ перейти к КНФ, и наоборот, можно применить законы дистрибутивности.
Пример: Приведите формулу к КНФ и ДНФ:
С помощью равносильных преобразований, используя законы логики
высказываний, получим:
- КНФ.
Перейдем от КНФ к ДНФ, используя закон дистрибутивности конъюнкции относительно дизъюнкции идемпотентностии и законы дополнительности:
– ДНФ
Замечание: Для того чтобы проверить правильно ли привели формулу к КНФ и ДНФ, можно построить таблицы истинности первоначальной и получившихся формул. Последние столбцы таблиц этих формул должны принимать одинаковые значения истинности.
5. Совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ).
Формула называется СДНФ, если:
1) она является ДНФ;
2) каждая элементарная конъюнкция ДНФ содержит все наименования переменных, от которых зависит формула, и каждое наименование входит в него один раз;
3) среди элементарных конъюнкций ДНФ нет одинаковых.
Примеры:
1. - СДНФ
2. - не является СДНФ, т.к. в первой скобке нет переменной Z.
Формула называется СКНФ, если
1) она является КНФ;
2) каждая элементарная дизъюнкция КНФ содержит все наименования переменных, от которых зависит формула и это наименование входит только один раз;
3) среди элементарных дизъюнкций КНФ нет одинаковых.
Пример:
- СКНФ
Теорема 1: Если формула не тождественно истинная, то для нее существует и при том единственная СКНФ.
Теорема 2: Если формула не тождественно ложная, то для нее существует и при том единственная СДНФ.
Совершенные формы можно строить с помощью:
1) равносильных преобразований;
2) таблиц истинности.
Алгоритм построения СДНФ с помощью таблице истинности:
Рассмотрим этот алгоритм на конкретном примере, используя таблицу истинности
X | Y | Z | F(x,y,z) |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
1) выбираем те строки таблицы , на которых формула принимает значение истина: 2, 4, 7, 8;
2) для каждой выбранной строки строим элементарную конъюнкцию из переменных, от которых зависит формула следующим образом: если переменная в строке принимает значение истина, то она непосредственно входит в элементарную конъюнкцию, если ложь, то она входит с отрицанием;
3) из элементарных конъюнкций составляем ДНФ.
- СДНФ
Замечание: Если все строки формулы в таблице истинности принимают значение ложь, то СДНФ построить нельзя.
Алгоритм построения СКНФ
по таблице истинности:
Данный алгоритм аналогичен алгоритму построения СДНФ.
1) выбираем строки таблицы, на которых формула принимает значение ложь: 1, 3, 5, 6;
2) для каждой выбранной строки строим элементарную дизъюнкцию из переменных, от которых зависит формула, следующим образом: если переменная в строке принимает значение ложь, то она сама входит в элементарную дизъюнкцию, если истина, то она входит с отрицанием;
3) из элементарных дизъюнкции составляем КНФ.
- СКНФ
Замечание: Если все строки формулы в таблице принимают значение истина, то СКНФ построить нельзя.
С точки зрения алгебры логики представление функции в виде СНКФ рациональнее, когда таблица истинности содержит меньше нулей , чем единиц
Описанный способ нахождения СНДФ и СНКФ исходной формулы по таблице истинности бывает более трудоёмким, чем следующий:
Алгоритм построения СДНФ с помощью равносильных преобразований:
1) приводим исходную формулу к ДНФ;
2) если в элементарную конъюнкцию некоторая переменная входит со своим отрицанием, то удаляем эту конъюнкцию из ДНФ;
3) если в элементарную конъюнкцию некоторая переменная входит несколько раз, то удаляем эти переменные кроме одной;
4) если в некоторую элементарную конъюнкцию некоторая переменная или переменные не входят, то заменяем её на эквивалентную форму, добавляя к ней одну или несколько переменных в виде и, применяя закон дистрибутивности, приводим формулу к ДНФ;
5) если в полученной ДНФ имеется несколько одинаковых элементарных конъюнкций, то оставляем только одну из них.
В результате получаем СДНФ.
Пример:
Пусть дана ДНФ функции . Найдте СДНФ функции.