Задания по практическим работам по темам Нахождение СДНФ и СКНФ и Применение алгебры высказываний к переключательным функциям по дисциплине ЕН.02 Дискретная математика с элементами матлогики для специальности 09.02.07 Информац. с-мы и программирование
план-конспект занятия

Практическая работа 7

Тема. Нахождение СДНФ и СКНФ.

Задание 1. Для формулы: ∨ y → ∧b ↔ 

(1) Построить истинностную таблицу;

(2) Используя результат, полученный в (1), построить СДНФ и СКНФ;

(3) Найти какие-нибудь ДНФ и КНФ;

(4) Привести найденные в (3) ДНФ и КНФ, соответственно, к СДНФ и СКНФ. Полученный результат сравнить с результатом, найденным в (2).

Задание 2. Для формулы: ∨ b → → 

(1) Построить истинностную таблицу;

(2) Используя результат, полученный в (1), построить СДНФ и СКНФ;

(3) Найти какие-нибудь ДНФ и КНФ;

(4) Привести найденные в (3) ДНФ и КНФ, соответственно, к СДНФ и СКНФ. Полученный результат сравнить с результатом, найденным в (2).

Примечание. Перед решением ознакомиться с лекциями 7-8.

Практическая работа 8

Тема. Применение алгебры высказываний к переключательным функциям.

Задание 1. Найти функцию проводимости следующей схемы, упростить ее и начертить упрощенную схему.

Задание 2. Найти функцию проводимости следующей схемы, упростить ее и начертить упрощенную схему.

Примечание. Перед решением ознакомиться с лекцией 9.

Лекция 8

Тема. Совершенные дизъюнктивная и конъюнктивная нормальные формы (СДНФ и СКНФ). Взаимосвязь пропозиционной и совершенной нормальной форм.

Формула называется совершенной КНФ (СКНФ) , если она является конъюнкцией различных полных элементарных дизъюнкций от высказывательных  переменных.

Теорема 7

 Всякая элементарная дизъюнкция высказывательных переменных , ,…,, не являющаяся тавтологией, эквивалентна СКНФ из этих переменных.

Док-во

Пусть А является элементарной дизъюнкцией, т.к. по условию, она не является тавтологией, то в нее н входит не одна переменная вместе со своим отрицанием.

Если какая-то переменная , входит в А несколько раз, то можно оставить ее только один раз, потому что  2-х одинаковых формул равносильно одной.

Если некоторая переменная  не входит в первоначальную  А, то ее можно ввести, добавив  заведомо ложной дизъюнктивный член, например ()=0

Таким образом, можно ввести все недостающие переменные и при этом получиться формула, предоставляются собой конъюнкцию полных элементарных дизъюнкций, т.е. совершенную КНФ, эквивалентную первоначальный дизъюнкции А.

Теорема 8

Всякая элементарная конъюнкция переменных , не являющегося противоречием, эквивалентна совещенной ДНФ из этих переменных.

Из этих 2-х теорем следует:

Следствие 1

Для всякой ДНФ, не являющегося тавтологией, и для всякой КНФ, не являющейся противоречиемсуществуют соответственно эквивалентные или совершенные КНФ и ДНФ для той же системы переменных. Из 1-ого следствия можно записать 2-ое следствие.

Следствие 2

Для всякой пары, не являющейся тавтологией или противоречием существуют соответственно эквивалентные ей СКНФ и СДНФ

Все совершенные КНФ и ДНФ  от n переменных:

1) представляют различные классы эквивалентных формул от этих переменных;

2) каждый класс представлен только одной СКНФ, кроме класса тавтологии.

Следовательно, для каждой формы можно найти СКНФ.

Аналогичные выводы можно получить относительно СДНФ.

Эти формулы хорошо тем что можно указать пути формулы.

Если произвольная НФ И задана своей таблицей истинности, то выбирая пути функции мы составим СКНФ, эквивалентную И,  а составленный СДНФ, эквивалентную первоначальной формуле И.

Наоборот, если мы имеем СНФ-ы  эквивалентные формуле И, то легко составить ее таблицу истинности.

Например, Пусть имеется таблица истинности переменных .

Выбираем пути функции запишем СКНФ

1)  – 010

2)  – 011

3)– 110

4)  – 111

Возьмем   = ()  ()  ()  () –СКНФ.

СКНФ эквивалента формуле U.

Теперь выберем единицы функции U и запишем СДНФ.

1)  – 000

2) – 001

3)  – 100

4)  – 101

= ()  ()  ()  () –СДНФ U.

Истинностные таблицы СДНФ и формулы U совпадают.

Если мы ищем СКНФ и СДНФ, то можно перейти к U. Для чего в СКНФ переменным без отрицания придают значение 0, а с отрицанием – 1, составляем таблицу U=0. В СДНФ без отрицания – 1, с отрицанием 0, составляем таблицу U=1.

СДНФ, содержащая все полные элементарные конъюнкции n - переменных, имеет в таблице истинности все значения равные, т.е. является тавтологией.

Аналогично, если СКНФ содержит все полные элементарные дизъюнкции n-переменных, то она является противоречием.

Для любой НФ можно сказать, будет ли она тавтологией или противоречием, либо ни тем, ни другим.

Для этого нужно рассматривать либо ее таблицу истинности, либо ее разложение в СНФ.

Понятие выводимости или логического следствия

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

Т.е. это значит, что у В, кроме этого, есть другие единицы, но это не значит, что А1.

Формула В является выводимой из последовательности  , если является тавтологией следующая импликация  В, это значит что импликация ложна, тогда, из истинной посылки ложное следует ложно В, такое положение не допускается. Т.е. при всех  =1, В=1.

Пусть эта импликация является тавтологией. Предположим, что все А = 0, а B≠ 1, тогда   будут истинны импликация принимает значение 0, но тогда она не является тавтологией, что противоречит предположению.

Следовательно, импликация является тавтологией.

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

Тавтологии тоже выводимы из любой системы формул.

Предположим, что В-тавтология, т.е =1. Тогда какое бы не принимала значение формула , В всегда истинна.

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

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

Мы доказали, что для того, чтобы B, необходимо и достаточно, чтобы   В и наоборот. B В.

Докажем 2-ое утверждение.

Пусть в системе не одна формула, а 2 или больше.

АВА(Вс)

Из этой тавтологии следует, что

 В).

Применим еще раз равносильность 26.

 В)). и  т.д

Если мы применим эту равносильность (m-1) раз, то мы получим

.

Лекция 9.

Тема. Применение алгебры высказываний к переключательным схемам

Простейшие схемы состоят из следующего:

1) вход схемы

2)устройство – переключатель

3) выход

Переключателем может быть выключатель или механический(будильник) переключатель.

Простейший переключатель

Можно поставить просто лампу, реле, кенотрон(меняет напряжение)

В качестве переключателя либо механический переключатель – рубильник, либо электронная лампа, либо реле, либо полупроводниковый прибор..

В такой схеме рассматриваются только 2 состояния:

1) переключатель замкнут

2) переключатель разомкнут

Т.е говорят: проходит ток или нет через схему.

Если так, тогда к каждому переключателю можно поставить соответственно высказывательную переменную.

pq оба замкнуты

pq

Для отрицанияток проходит когда p≤0, bне проходит при p≤1

Каждый переключательной схеме будет соответствовать эквивалентная формула.

Вывод:

1. Каждая формула в алгебре высказываний может быть представлена эквивалентной ей переключательной схемой.
2. Для каждой переключательной схемы можно построить эквивалентную ей логическую функцию.

а) эта схема ток пропускать не будет.

б) эта схема всегда будет проводить ток. Она соответсвует такой логической функции p

Рассмотрим несколько примеров.

Рассмотрим логическую функцию такую

U = (pqz)(st) = (st)

Упрощение этой схемы

Пусть имеется такая схема

запишем советующую ей формулу.

(pqz)(p)(qsz)(q)=p((qz))) (q (sz)))=

= (p (q) ())(q (z) ())=(p (q)) (q (z))

                                        =1                                          =1

Теперь составим схему, соответствующую упрощенной формуле.