Каков порядок составления таблицы истинности для сложной формулы?

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

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

Запишите аксиомы одиночных элементов (1-я группа аксиом).

Аксиомы одиночных элементов:

1) ; 2) ;

3) ; 4) .

Запишите аксиомы и законы отрицания (2-я группа аксиом).

Аксиомы и законы отрицания:

1) ; 2) (закон противоречия);3) (закон исключенного третьего);

 

4) ; 5) (законы де Моргана).

Запишите комбинационные законы алгебры логики (3-я группа аксиом).

Комбинационные законы:

1) (общий случай ); законы идемпотентности

2) (общий случай );

– переместительные законы;

– сочетательные законы.

– сочетательные

В чем суть полноты систем логических операций? Приведите 3 функционально полные системы операций.

Отметим еще одно чрезвычайно важное свойство функциональной полноты системы операций. Если любую формулу алгебры логики можно свести к некоторой другой равносильной формуле, содержащей только определенную систему операций, то такая система операций называется функционально полной системой операций (ФПСО) или базисной. В алгебре логики такой ФПСО являются системы операций: .

Правила склеивания для элементарных конъюнкций и дизъюнкций. Примеры.

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

Например: – элементарное произведение,

– неэлементарное произведение.

Количество сомножителей в элементарном произведении называется его рангом.

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

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

Пример:

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

Пример:

Правила поглощения для элементарных конъюнкций и дизъюнкций. Примеры.

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

Пример:

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

Пример: .

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

Правило развертывания для элементарных конъюнкций и дизъюнкций. Примеры.

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

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

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

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

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

1.

2. .

3.

= .