Таблиці істинності

Таблиці, в яких кожній інтерпретації функції (x₁, x₂,…x_n) поставлено у відповідність її значення, називаються таблицями істинності булевої функції.

В таблиці кожній змінній та значенню функції відповідає по одному стовпчику, а кожній інтерпретації – один рядок.

х	j0	j1	j2	j3

Наведемо вигляд таблиці для n=1:

Тобто j₁(1) = 1; j₂(1) = 0; j₂(0) = 1;

Наведемо вигляд таблиці для n=2:

х

у

j0

j1

j2

j3

j4

j5

j6

j7

j8

j9

j10

j11

j12

j13

j14

j15

Тобто j₁(1, 0) = 0; j₁₂(1,0) = 0; j₆(0,1) = 1.

Кожній функції присвоюється порядковий номер у вигляді натурального числа, двійковий код якого зображує стовпчик значень відповідної функції. Наприклад, для функції j₁₂ для числа 12 = 1100₂ і для 1-ї інтерпретації j₁₂(0,0) = 1, j₁₂(0,1) = 1, j₁₂(1,0) = 0, j₁₂(1,1) = 0.

Більшість із розглянутих функцій часто використовують на практиці і мають певні позначення:

Функція	Позначка	Назва	Інші познач.	прочитання
j0(х, у)		Константа 0
j1(х, у)	хÙу=ху	Кон’юнкція (логічне і)	&,AND,min	х і у
j2(х, у)	ху	Заперечення імплікації	\	х і не у
j3(х, у)	х	Повторення першого аргументу		як х
j4(х, у)	ух	Заперечення оберненої імплікації	\	не х і у
j5(х, у)	у	Повторення другого аргументу		як у
j6(х, у)	хÅу	Виключає «або» (сума за модулем 2)	¹, XOR	х не як у
j7(х, у)	хÚу	Диз’юнкція (логічне «або»)	OR,+,max	х або у
j8(х, у)	х¯у	Заперечення диз’юнкції (стрілка Пірса)		не х і не у
j9(х, у)	х~у	Еквівалентність	Û, º	х як у
j10(х, у)		Заперечення другого аргументу	Øy	не у
j11(х, у)	у®х	Обернена імплікація	Ì	х, якщо у
j12(х, у)		Заперечення першого аргументу	Øx	не х
j13(х, у)	х®у	Імплікація	Þ	якщо х, то у
j14(х, у)	x | y	Заперечення імплікації (штрих Шеффера)		не х або не у
j15(х, у)		Константа 1

Випишемо таблиці істинності для окремих логічних бінарних функцій f_n(x, y).

х	у	хÚу

Диз’юнкція дає в результаті 1, якщо хоч один операнд дорівнює 1. Диз’юнкцію часто називають логічним додаванням, тому часто замість знака Ú використовують знак +.

Диз’юнкція 3-х і більше операндів також дає 1 в результаті, якщо хоч один з операндів має значення 1. Чотирьом інтерпретаціям відповідає код стовпчика результатів 0111, що є двійковим кодом числа 7, тобто в таблиці операція диз’юнкції приведена як j₇(х, у).

х	у	хÙу

Кон’юнкція дає в результаті 1, якщо всі операнди мають значення 1. Операцію також називають логічним множенням і замість позначки Ù використовують знак ·.

Кон’юнкція 3-х і більше операндів також дає 1 в результаті, якщо всі операнди мають значення 1. Чотирьом інтерпретаціям відповідає код стовпчика результатів 0001, що є двійковим кодом числа 1, тобто в таблиці операція кон’юнкції приведена як j₁(х, у).

х

Інверсія (заперечення) значення х має значення протилежне х. Це унарна операція в таблиці приведена як j₂(х). Аналогом позначки є позначка Øх.

х	у	х®у

Імплікація дає в результаті 0 тільки в одній інтерпретації (1, 0). Чотирьом інтерпретаціям відповідає код стовпчика результатів 1101, що є двійковим кодом числа 13, тобто в таблиці операція імплікація приведена як j₁₃(х, у).

х	у	х~у

Еквівалентність дає в результаті 1 тільки в інтерпретаціях (0, 0) і (1, 1). Чотирьом інтерпретаціям відповідає код стовпчика результатів 1001, що є двійковим кодом числа 9, тобто в таблиці операція еквівалентність приведена як j₉(х, у).

х	у	хÅу

Сума за модулем 2 дає в результаті 1 тільки в інтерпретаціях (0, 1) і 1, 0). Чотирьом інтерпретаціям відповідає код стовпчика результатів 0110, що є двійковим кодом числа 6, тобто в таблиці операція імплікація приведена як j₆(х, у).

Для самостійної роботи

Критерії оцінювання: Кожне завдання – 4 бали. Максимальна кількість балів – 12.

Завдання 1. Визначити значення функції:

Варіант
А)	j0(0)	j3(1)	j2(0)	j1(0)	j0(1)	j2(1)
Б)	j10(1,0)	j13(0,0)	j11(0,1)	j9(1,1)	j14(0,1)	j7(0,0)

Завдання 2. Скласти таблицю істинності функції:

Варіант
jn(x, y)	х~у	хÅу	х¯у	х®у	x | y	ху

Завдання 3. Визначити значення логічного виразу:

Варіант
А)	1Ú1	0Ú1	0Ú0	1Ù0	1Ù1	0Ù1
Б)	1Å0	1~0	1 | 0		1¯1	0®0

Самостійна робота № 9

Тема: Складання таблиць істинності до булевих функцій

Мета: Закріпити набуті знання та навички, перевірити їх при виконанні практичних завдань.