2. Логические функции (Булевы функции) Пример: Устройство для голосования. Комиссия из 3-х человек, (Peeter, Jaan, Mari), голосует по вопросу о принятии. - презентация

1 2. Логические функции (Булевы функции) Пример: Устройство для голосования. Комиссия из 3-х человек, (Peeter, Jaan, Mari), голосует по вопросу о принятии некоторого решения. Решение принимается простым большинством голосов. Высказывание A: Peeter голосует за Высказывание B: Jaan голосует за Высказывание C: Mari голосует за Высказывание D: Решение принято 2.1. Перехед от логики высказываний на язык логических функций Джордж Буль ( ) английский математик и логик

2 ABCD Таблица истинности (зависимость принятия решения D от значений A, B и C) :

3 Пусть голосование происходит с помощью дигитального устройства: Peeter нажимает на кнопку устройства (за или против). Кнопка связана с двоичным входом устройства X 1, который принимает соответственно значение "1" или "0". Это отображение высказывания A. Отображениями высказываний B и C являются двоичные переменные X 2 и X 3. Результат (высказывание D) выражается логической функцией f(X 1, X 2, X 3 ). дигитальное устройство Peeter Jaan Mari результат вход выход

4 X1X1 X2X2 X3X3 f(X 1, X 2, X 3 ) дигитальное устройство X1X1 X2X2 X3X3 f(X 1, X 2, X 3 ) вход выход

5 В дальнейшем: Вместо высказываний A, B, C,... – используем логические переменные X 1, X 2,..., X n,...,где каждая переменная X i, i = 1, 2,..., n,... X i Вместо формул – логические функции f (X 1, X 2,..., X n ) 0 Определение 2.1 логическая функция n переменных f (X 1, X 2,..., X n ) ставит в соответствие каждому двоичному вектору (или аргумент-вектору) (X 1, X 2,..., X n ) 0,1 n логическое значение 0 или 1: При этом каждую последовательность длины n: (X 1, X 2,..., X n ) называем двоичным вектором.

6 Частные случаи: n = 2 функция 2-х переменных f (X 1, X 2 ) – это следущее соответствие ( 2 2 = 4) 0 1 множество всех двоичных векторов длины n, ( 2 n ) 0 1

7 Пример: f (X 1, X 2 ) = (X 2 X 1 ) X 1, X 2 f (X 1, X 2 ) f (X 1, X 2 ) Таблица истинности: диаграмма соответствия

8 n = 3 функция 3-х переменных f (X 1, X 2, X 3 ) – это следущее соответствие ( 2 3 = 8) 0 1

9 Пример: f (X 1, X 2, X 3 ) = X 1 &X 2 X 2 & X 3 X 1, X 2, X 3 f (X 1, X 2, X 3 ) Таблица истинности:

10 f (X1, X2, X3) Диаграмма соответствия:

11 Число всех различных логических функций f(X 1,X 2,...X n ) : n = 1 K = 4 n = 2 K = 16 n = 3 K = 256 n = 4 K = Если n = 1, то всех различных логических функций K = 4 : X1X1 f1f1 f2f2 f3f3 f4f

12 Перечислим все 16 различных логических функций 2-х переменных f(X 1, X 2 ): x1x1 x2x2 f0f0 f1f1 f2f2 f3f3 f4f4 f5f5 f6f6 f7f x1x1 x2x2 f8f8 f9f9 f 10 f 11 f 12 f 13 f 14 f

13 В таблице представлены следущие логические функции: f 0 (X 1, X 2 ) = 0 = X 1 & X 1 & X 2 f 1 (X 1, X 2 ) = X 1 & X 2 f 2 (X 1, X 2 ) = (X 1 X 2 ) f 3 (X 1, X 2 ) = X 1 = X 1 ( X 2 & X 2 ) f 4 (X 1, X 2 ) = (X 2 X 1 ) f 5 (X 1, X 2 ) = X 2 = X 2 ( X 1 & X 1 )......

14 Логические функции f 1 и f 2 равносильные, если для каждого аргумент-вектора ( X 1, X 2,..., X n ) f 1 (X 1, X 2,..., X n ) = f 2 (X 1, X 2,..., X n ). Области истинности логических функций: Область 1-ниц логической функции V 1 образуют те аргумент- векторы ( X 1, X 2,..., X n ), для которых f(X 1, X 2,..., X n )=1 Область 0-лей логической функции V 0 образуют те аргумент-векторы ( X 1, X 2,..., X n ), для которых f(X 1, X 2,..., X n )=0 Логическая функция тождественно истинная (тавтология), если для каждого аргумент-вектора ( X 1, X 2,..., X n ) f(X 1, X 2,..., X n )=1. Логическая функция тождественно ложная (противоречие), если для каждого аргумент-вектора ( X 1, X 2,..., X n ) f(X 1, X 2,..., X n )=0.

15 по области 1-ниц: f(X 1, X 2, X 3 ) = (1, 6, 7) 1 – означает, что в 1-ой, 6-ой и 7-ой строках таблицы истинности 1-цы, в остальных строках 0- ли. по области 0-ей: f(X 1, X 2, X 3 ) = (0, 3, 5) 0 – означает, что в 0-ой, 3-ей и 5-ой строках таблицы истинности 0-ли, в остальных строках 1- цы. Cпособы представления логических функций : Таблица истинности Логическое выражение Числовое десятичное представление

16 Теорема 2.1: каждую логическую функцию можно представить a) дизъюнкцией конъюнкций; b) конъюнкцей дизъюнкциий. Доказательство: a) алгоритм представления дизъюнкцией конъюнкций (4 шага): 1. шаг: по формуле 9.a) заменить все - ции через &-ции, -ции и -ия. 2. шаг: по формуле 8.a) заменить все - ции через -ции и -ния. 3. шаг: если стоит перед скобками, то внести отрицание в скобки по формулам 7.a) или 7.b) (законы дe Moргана): (... &... &...) ( ) (... &... &...) 7.b) 7.a) 4. шаг: если в результате получится конъюнкция дизъюнкциий, то применить дистрибутивность 4.a) и перемножить скобки: ( ) & ( ) &... (... &... &...) (... &... &...)... 4.a)

17 b) алгоритм представления конъюнкцей дизъюнкциий(4 шага): 1. шаг: по формуле 9.a) заменить все - ции через &-ции, -ции и -ия. 2. шаг: по формуле 8.a) заменить все - ции через -ции и -ния. 3. шаг: если стоит перед скобками, то внести отрицание в скобки по формулам 7.a) или 7.b) (законы дe Moргана): (... &... &...) ( ) (... &... &...) 7.b) 7.a) 4. шаг: если в результате получится дизъюнкция конъюнкциий, то применить дистрибутивность 4.b) и перемножить скобки: ( ) & ( ) &...(... &... &...) (... &... &...)... 4.b) Teoрема доказана.

18 Примеры: представить логическую функцию a) дизъюнкцией конъюнкций 1) ( (X 1 X 2 ) ( X 1 X 2 ))&X 2 2) ((X 1 X 2 )&( X 2 X 3 )) (X 3 X 1 ) b) конъюнкцей дизъюнкциий 1) X 1 &X 3 X 2 &X 3 X 1 &X 2 &X 3 X 1 & X 3 2) (X 1 X 2 ) ((X 1 & X 2 ) X 3 ) Решение: a) дизъюнкцией конъюнкций 1) ( (X 1 X 2 ) ( X 1 X 2 ))&X 2 = ( ( X 1 X 2 ) ( X 1 X 2 ))&X 2 = =(( X 1 X 2 ) ( X 1 X 2 ))&X 2 = ( X 1 X 2 )&X 2 = X 1 &X 2 X 2 &X 2 = = X 1 &X 2 X 2. 8.a) 5.b)4.a) 5.a)

19 2) ((X 1 X 2 )&( X 2 X 3 )) (X 3 X 1 ) = = (( X 1 X 2 )&( X 2 X 3 )) ( X 3 X 1 ) = = ( ( X 1 X 2 ) ( X 2 X 3 )) ( X 3 & X 1 ) = = (( X 1 & X 2 ) ( X 2 & X 3 )) (X 3 & X 1 ) = = X 1 & X 2 X 2 & X 3 X 1 & X 3. 8.a) 7.b)7.a) 7.b) b) конъюнкцей дизъюнкциий 1) (X 1 &X 3 X 2 &X 3 ) ( X 1 &X 2 &X 3 X 1 & X 3 ) = = [(X 1 X 2 )&(X 1 X 3 )&(X 3 X 2 )&(X 3 X 3 )] [( X 1 X 1 )& ( X 1 X 3 )&(X 2 X 1 )&(X 2 X 3 )&(X 3 X 1 )& (X 3 X 3 )] = = (X 1 X 2 X 1 X 3 )&(X 1 X 2 X 2 X 1 )&(X 1 X 2 X 2 X 3 )&(X 1 X 2 X 3 X 1 )& & (X 3 X 1 X 3 )&(X 3 X 2 X 1 )&(X 3 X 2 X 3 )&(X 3 X 3 X 1 ) = 4.b) 5.b) b) 11.a) b)

20 = (X 1 X 2 )&(X 1 X 2 X 3 )&(X 1 X 2 X 3 )&(X 3 X 2 X 1 )&(X 3 X 1 ) = = (X 1 X 2 )&(X 1 X 2 )&(X 3 X 1 ) = 10.b)11.a) 5.a) = (X 1 X 2 )&(X 3 X 1 ). 2) (X 1 X 2 ) ((X 1 & X 2 ) X 3 ) = 8.a) (X 1 X 2 ) ( (X 1 & X 2 ) X 3 ) = = ( X 1 & X 2 ) (( X 1 X 2 ) X 3 ) = 7.a)7.b) ( X 1 & X 2 ) ( X 1 X 2 X 3 ) = 4.b) = ( X 1 X 1 X 2 X 3 ) & (X 2 X 1 X 2 X 3 ) = 5.b) = ( X 1 X 2 X 3 ) & ( X 1 X 2 X 3 ) = 5.a) = X 1 X 2 X 3.