Основні закони алгебри логіки.

В алгебрі логіки існують логічні закони, логічні суперечності, або твердження, що логічно виконуються.

* Логічним законом називається складне висловлення, яке є істинним при всіх можливих комбінаціях значень, висловлень які до нього входять.

 

* Логічною суперечністю називається складне висловлення яке є завжди хибним, при всіх можливих комбінаціях значень, висловлень, які до нього входять.

 

* Твердженням, що логічно виконується називається складне висловлення, яке є істинним для одних значень простих висловлень і хибним для інших значень простих висловлень.

 

Основні закони алгебри логіки:

Назва закону	Логічний запис
1) Тотожність 2) Суперечності 3) Виключеного третього 4) Ідемпотентності 5) Комутативний   6) Асоціативний   7) Дистрибутивний 8) Поглинання   9) Де Моргана (подвійності)   10) Подвійного заперечення 11) Властивість одиниці   12) Властивість нуля	А А =1 + = 1 =1; А+А=А. А+В=В+А; (АВ)С=А(ВС) А+(В+С)=(А+В)+С (А+В)·С= АС+ВС А(А+В)=А А+АВ=А = = + А·1=А А+1=1 А+0=А

 

 

4. Логічна функція.

* Логічною називаєтьсяфункція F від n змінних, х₁...х_n, яка так само, як і аргументи може набирати лише два значення 0 і 1. х₁; х₂;... х_n – аргументи функції.

 

· Набором називається сукупність а₁;а₂;...а_n значень змінних х₁; х_2;.... х_n.

 

Теорема: Кількість наборів для аргументів х₁; х_2;.... х_n логічної функції N=2ⁿ

 

Набори для аргументів х₁; х_{2 .}

 

№ набору	x1	x2

Теорема: Кількість різних логічних функцій від n аргументів

Якщо n=1 (одна змінна), то N=2; M=2²=4

Якщо n=2 (дві змінних), то N=2²=4; М=2⁴=16

 

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

для одного аргументу існують 4 різні логічні функції

 

№ набору	Змінна	Логічні функції
А	F=0	F=1	F=	F=А

для двох змінних А і В існує N=2²=4 набори і М=16 логічних функцій.

 

№ набору

змінні

Логічні функції

А

В

 

1) F=0 5) F=А B 9) F=A B 13) F=A~B

2) F=1 6) F=A│B 10) F=A B 14) F=A B

3) F=A 7) F=A B 11) F=B A 15) F=

4) F=B 8) F=A B 12) F=B A 16) F=

Розглянуті 16 логічних функцій для двох змінних носять назву елементарних. Це ті функції, на основі яких будується алгебра логіки і її застосування в науці і техніці. Серед цих 16 функцій є базисні, за допомогою яких одержують інші функції.

 

Базисні:

1/ F=1

2/ F=0

3/ F=A

4/ F=A→B (інверсія)

5/ F=

6/ F=

 

Для елементарних функцій існує ряд важливих формул, які перевіряються в таблицях істинності:

1) Правило Де Моргана: =

 

А	В				А В

 

2) Правило Де Моргана: =

3) A B = B

4) A ~ B= ( )()

У разі коли одним з аргументів є F=1, або F=0, то справедливі слідуючи співвідношення:

 

№ п/п	X і 1	X і 0

 

Співвідношення для аргументів Х₁ і Х₂:

 

№ п/п	Х1=Х2=Х	Х1=Х; Х2=
	I	│ =1

Бульові функції.

Якщо взяти будь-яку формулу алгебри висловлень, то її значення істинності буде функцією значень істинності простих висловлень з яких вона складається. Ця функція має властивість: вона сама і її аргументи набувають лише двох значень 0 і 1. Такі функції називаються двозначними або бульовими функціями.

Назва дана в честь англійського математика дев’ятнадцятого століття Джорджа Буля, що заклав основи бульової алгебри.

Область значень бульової функції і її аргументів складається з двох елементів: істинності і хибності, а область існування (визначення) – з n- місних наборів.

 

Приклади бульових функцій в науці і практиці:

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

 

Отже значення бульової функції і її аргументів найрізноманітніші:

- істинність – хибність;

- так – ні;

- струм проходить – не проходить;

- лампа горить – не горить і т. д.

Аргументи бульової функції називаються бульовими змінними.

Різниця між бульовими функціями і алгеброю висловлень:

- алгебра висловлень розглядає тільки функції істинності висловлень, тобто обме жена чисто логічним матеріалом;

- теорія бульових функцій відкидає обмеженість і виходить на широкий простір будь-яких двозначних зв’язків між будь-якими предметами (об’єктами);

- закони теорії бульових функцій мають більш загальний характер і знаходять

більше застосувань в науці і практиці;

- теорія бульових функцій вийшла за межі чистої логіки.

Алгебра висловлень – це лише одна з галузей теорії бульових функцій.

Теорія бульових функцій застосовується в:

- релейно-контактних схемах;

- дискретних автоматах;

- електронно-цифрових обчислювальних машинах;

- деяких питаннях математики.

Бульова алгебра – це множина бульових функцій, які розглядаються разом з трьома основними операціями:

- кон’юнкцією;

- диз’юнкцією;

- запереченням.

Ці операції називаються бульовими, а формули бульової алгебри – бульовими формулами.

 

Основні формули бульової алгебри:

№ п/п	Формули для диз’юнкцій	Формули для кон’юнкцій	Формули для заперечень

 

Спеціальні формули бульової алгебри:

(закон контрапозиції).

Контрольні запитання.

1. Що таке математична логіка?

2. Що називається висловленням? Наведіть приклади.

3. Яке висловлення називається простим, складним? Наведіть приклади

4. Сформулювати означення основних логічних операцій, їх таблиці істинності.(*)

5. Що називається логічним законом?

6. Що називається логічною суперечністю?

7. Що називається твердженням, що логічно виконується?

8. Назвати та записати основні закони алгебри логіки. (**)

9. Яка функція називається логічною?

10. Які функції є базисними?

11. Яка функція називається бульовою?

12. Де застосовується теорія бульових функцій?

13. Записати основні формули бульової алгебри.(*)

 

Література:

О.А. Борисенко. Лекції з дискретної математики: навчальний посібник для вузів. Суми, СумДУ, 1999р. лекції 11 - 13

Ю.В. Нікольський, В.В.Пасічник, Ю.М. Щербина. Дискретна математика. Підручник для вищих навчальних закладів. Київ. 2007р. розділ 1. п. 1.1 – 1.8

М.М.Швець. Азбука математичної логіки. Київ. 1965р. розділ 1,