Курсовая работа: Спеціальні класи та функціональна повнота системи функцій алгебри логіки. Теорема Поста

Таблиця №2

№	X= 0 Y= 0	0 1	1 0	1 1	fк (X,Y)
1	0	0	0	0
2	0	0	0	1
3	0	0	1	0
4	0	0	1	1
5	0	1	0	0
6	0	1	0	1
7	0	1	1	0
8	0	1	1	1
9	1	0	0	0
10	1	0	0	1
11	1	0	1	0
12	1	0	1	1
13	1	1	0	0
14	1	1	0	1
15	1	1	1	0
16	1	1	1	1

Більшість із шістнадцяти булевих функцій f(x, у) часто застосовуються на практиці. Оскільки дані функції використовуються як у математиці, так і в програмуванні, вони можуть мати різне позначення.

Позначення булевих функцій та їх назви.

Таблиця №3

Функція	Позначення	Назва
	0	константа 0
		Кон'юнкція (логічне «і») — двомісна логічна операція, що має значення «істина», якщо всі операнди мають значення «істина». Операція відображає вживання сполучника «і» в логічних висловлюваннях. Позначається в програмуванні як & чи and.
		заперечення імплікації
		Повторення першого аргументу
		заперечення оберненої імплікації
	У	Повторення другого аргументу
	ху	Виключна диз'юнкція (XOR, додавання за модулем два) — двомісна логічна операція, що приймає значення «істина» тоді і тільки тоді коли значення «істина» має рівно один з її операндів. Виключна диз'юнкція є запереченням логічної еквівалентності.
		Диз'юнкція (логічне «або») — двомісна логічна операція, що має значення «істина», якщо хоча б один з операндів має значення «істина». Операція відображає вживання сполучника «або» в логічних висловлюваннях. Позначається в програмуванні як or.
		Стрілка Пірса (операція NOR) — двомісна логічна операція, яка є запереченням диз'юнкції; тому значення «істина» одержується тільки тоді, коли обидва операнди мають значення «хиба».
		Еквівалентність — двомісна логічна операція, що має значення «істина», якщо обидва операнди мають однакове значення. Операція відображає вживання сполучника «тоді і тільки тоді» в логічних висловлюваннях.
		заперечення другого аргументу
		обернена імплікація
		заперечення першого аргументу
		Імплікація – двомісна логічна операція, що має значення «хиба», тоді і тільки тоді, коли перший операнд має значення «істина», а другий — «хиба».
		Штрих Шеффера (операція NAND) — двомісна логічна операція, яка є запереченням кон'юнкції; тому значення «хиба» одержується тільки тоді, коли обидва операнди мають значення «істина».
	1	константа 1

1.2 Функціональна повнота

Визначення. Множина функцій алгебри логіки А називається повною системою (в Р₂ ), якщо будь-яку функцію алгебри логіки можна виразити формулою над А.

Теорема 1[1, ст.6]. Система А={} є повною.

Доведення. Якщо функція алгебри логіки відмінна від тотожного нуля, то f виражається у вигляді досконалої диз’юнктної нормальної форми, в яку входять лише диз’юнкція, кон’юнкція та заперечення. Якщо ж , то . Теорема доведена.

Лема 1[1, ст.6]. Якщо система А – повна, і будь-яка функція може бути виражена формулою над іншою системою В, то В – теж повна система.

Доведення. Розглянемо довільну функцію алгебри логіки і дві системи функцій А={g₁ , g₂ ,…} і B={h₁ , h₂ ,…}. Оскільки система А повна, функція може бути виражена у вигляді формули над нею , де , тобто функція представляється увигляді , що означає що вона може бути представлена формулою над В. Перебираючи таким чином всі функції алгебри логіки, отримаємо, що система В також повна. Лема доведена.

Теорема 2[1, ст.6]. Такі системи є повними в Р₂

1. ;

2. ;

3. ;

4.

Доведення.

1. Відомо (теорема 1), що система А= повна. Покажемо, що система В= повна. З закону де Моргана отримуємо, що , тобто кон’юнкція виражається через диз’юнкцію і заперечення, і всі функції системи А виражаються формулами над системою В. Система В повна (лема 1).

2. Аналогічно пункту 1: = із леми 1 випливає, що вираз пункту 2 є правильний.

3. згідно леми 1 система повна.

4. згідно леми 1 система повна.

Розділ 2. Спеціальні класи функцій алгебри логіки