17. Как задать функцию алгебры логики в виде таблицы истинности и формулы? Сколько существует логических функций от n переменных?

Каждую функцию алгебры логики (как и формулу алгебры логики) можно задать с помощью таблицы истинности.

Алгоритм построение таблицы истинности:

1. Подсчитать количество переменных n в логическом выражении.

2. Определить число строк в таблице, которое равно m = 2ⁿ.

3. Подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице: количество переменных + количество операций = количество столбцов.

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

5. Заполнить столбцы входных переменных наборами значений.

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

Пример: A&(B˅^¬C)

Количество логических переменных 3, следовательно, количество строк в таблице истинности должно быть m=2³=8.

Количество логических операций в формуле 3, следовательно, количество столбцов в таблице истинности должно быть 3+3=6.

Двоичные наборы аргументов записываются в лексикографическом порядке.

A	B	C	^¬C	B˅^¬C	A&(B˅^¬C)
0	0	0	1	1	0
0	0	1	0	0	0
0	1	0	1	1	0
0	1	1	0	1	0
1	0	0	1	1	1
1	0	1	0	0	0
1	1	0	1	1	1
1	1	1	0	1	1

18. Опишите понятие «булева алгебра логических функций». Опишите правила основные свойства операций, представленных в булевой алгебре. Примените эти правила для упрощения формул.

Булева алгебра логических функций – алгебра (P2; ˅, &,¬), основным множеством которой является все множество логических функций, а операциями – дизъюнкция, конъюнкция и отрицание.

Основные правила булевой алгебры:

• Ассоциативность:

1. x₁(x₂x₃)=(x₁x₂)x₃

2. (x₁˅x₂) ˅x₃=x₁˅(x₂˅x₃)

• Коммутативность:

1. x₁x₂=x₂x₁

2. x₁˅x₂=x₂˅x₁

• Дистрибутивность:

1. & относительно ˅ x₁(x₂˅x₃)=x₁x₂˅x₁x₃

2. ˅ относительно & x₁˅ (x₂x₃)=(x₁˅x₂)(x₁˅x₃)

• Идемпотентность:

1. xx=x

2. x˅x=x

• Двойное отрицание:

¬¬x=x

• Свойства констант:

1. x&1=x

2. x&0=x

3. x˅1=1

4. x˅0=x

5. ¬0=1

6. ¬1=0

• Правила де Моргана:

1. ¬(x₁x₂)=¬x₁˅¬x₂

2. ¬(x₁˅x₂)=¬x₁¬x₂

• Закон противоречия:

x¬x=0

• Закон «исключение третьего»:

x˅¬x=1

Упрощение формул (т.е. получение эквивалентных формул, содержащих меньшее число символов).

1. Поглощение:

x˅xy=x

x(x˅y)=x

Д оказательство: x˅xy=x&1˅xy=x(1˅y)=x&1=x

x(x˅y)=xx˅xy=x˅xy=x

2. Склеивание:

xy˅x¬y=x

Доказательство: xy˅x¬y=x(y˅¬y)=x&1=x

19. Дайте определения сднф и скнф. Как построить такие представления для произвольной логической функции, заданной таблицей истинности или формулой?

• Простой конъюнкцией называется конъюнкция одной или нескольких переменных, при этом каждая переменная встречается не более одного раза (либо сама, либо ее отрицание). Например,      является простой конъюнкцией,

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций. Например, выражение          является ДНФ.

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

• Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание). Например, выражение         – простая дизъюнкция,

К онъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций (например, выражение             – КНФ).

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

Н апример, выражение               является СКНФ.

Как построить СДНФ и СКНФ функции, заданной таблицей, пример:

x1	x2	x3	φ( x1, x2, x3)
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

Для построение СДНФ нужно выписать все наборы, на которых функция равна 1: 000, 010, 101, 110. Для каждого набора построим элементарную конъюнкцию, равную единице на этом наборе:

Соединяя эти конъюнкции знаками дизъюнкции, получаем СДНФ заданной функции:

Д ля построение СКНФ выписываем все наборы, на которых функция равна нулю: 001, 011, 100, 111. Для каждого набора построим элементарную дизъюнкцию, равную нуля на этом наборе:

О бъединяя с помощью конъюнкции все элементарные дизъюнкции, получаем КСНФ заданной функции: