Все КЕ для двух высказываний

Высказывания	КЕ

 

 

Таблица 8

Все КН для двух высказываний

Высказывания	КН

Развёртывание элементарных конъюнкций

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

2. Каждая единица представляется в виде , где – высказывание, отсутствующее в исходной конъюнкции.

3. Производится раскрытие всех скобок на основе распределительного закона 1-го рода, что приводит к развертыванию исходной конъюнкции ранга в логическую сумму КЕ.

Пример. Развернуть конъюнкцию . Здесь предполагается, что число высказываний , но два из них отсутствуют, тогда:

1.

2. .

3.

= .

 

Развёртывание элементарной дизъюнкции

1. В развертываемую дизъюнкцию ранга вводится n-r нулей.

2. Каждый нуль представляется произведением , где – высказывание, отсутствующее в исходной дизъюнкции.

3. Полученная сумма преобразуется с помощью распределительного закона 2-го рода в логическое произведение КН.

Пример. Развернуть дизъюнкцию . Здесь число высказываний , отсутствует высказывание :

 

Упражнения

1. Используя алгебраические преобразования, доказать тождественную истинность или тождественную ложность формул:

1) ; 2) ; 3) ;

4) ; 5) ;

6) ; 7) ; 8) ;

9) .

 

2. Доказать равносильности формул, не используя таблицы истинности:

1) ; 2) ; 3) ; 4) ;

5) ; 6) ; 7) ;

8) ; 9) ; 10) ;

11) .

3. Упростить формулы:

1) 2) ; 3) ; 4) ;

5) ;

4.Привести следующие ниже формулы к базиса

1) ; 2) ; 3) .

5. Развернуть конъюнкцию:

1) ; 2)

Развернуть дизъюнкцию:

3) ; 4)

1. 5. Функции алгебры логики. Нормальные формы логических

Функций

Логическая функция [функция алгебры логики (ФАЛ)] – это выражение, представляющее собой сложное высказывание, состоящее из нескольких простых высказываний , связанных соединительными словами. Это сложное высказывание принимает значения 0 или 1 на всех наборах логических значений всех простых высказываний.

Как нетрудно заметить, приведенное определение ФАЛ полностью совпадает с определением формулы, данным в подразделе 1.3. Таким образом, всякая формула алгебры логики есть функция алгебры логики, в которой простые высказывания воспринимаются уже как переменные . Это правомочно, так как каждое из них принимает два значения: 0 или 1. А в зависимости от этого логические значения выражения тоже будут принимать значения 0 или 1, т.е. выражение является функцией в общепринятом смысле.

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

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

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

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

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

НДФ – это дизъюнкция нескольких элементарных конъюнкций. Эта форма называется нормальной, так как все ее члены имеет вид элементарных конъюнкций. Вследствие того, что все члены соединены в одну функцию знаком дизъюнкции, форма носит название дизъюнктивной. И, наконец, форма называется совершенной, если её члены имеют высший ранг, являясь конституентами единицы или нуля.