Реферат: Елементи логіки

Обчислимо значення формули, наприклад, (A®B)&(B®A) при всіх можливих наборах значень змінних A і B. Обчислення подамо такою таблицею:

A B	A®B	B®A	(A®B)&(B®A)
0 0	1	1	1
0 1	1	0	0
1 0	0	1	0
1 1	1	1	1

Таблиці, в яких представлено залежність значень формул від пропозиційних змінних, називаються таблицями істинності.

Розглянемо узгодження, які дозволяють скорочувати запис формул. Пропозиційні зв'язки упорядковуються за "силою тяжіння до формул" подібно до знаків арифметичних операцій. Всі розуміють, що вираз 1+2´3 позначає суму 1 і 2´3, а не добуток 1+2 і 3, тобто знак множення "притягується" сильніше за знак додавання. Зв'язка Ø вважається найсильнішою, тобто ØAÙB є скороченням від (ØA)ÙB, а не від Ø(AÙB). Далі за спаданням "сили тяжіння" двомісні зв'язки ідуть у такому порядку: &, Ú, ®, º. Отже, формулу AÚBÙC можна розглядати, як скорочений запис формули AÚ(BÙC), а формулу AºB®CÚA – як Aº(B®(CÚA)).

Всі двомісні зв'язки мають властивість лівобічного зв'язування. Це означає, що якщо праворуч і ліворуч від підформули записано без дужок знаки двомісних зв'язок, "сила тяжіння" яких однакова, то першою до підформули застосовується ліва з них. Наприклад, AÚBÚC є скороченим записом формули (AÚB)ÚC.

Означення. Дві формули називаються еквівалентними, або рівносильними, якщо приймають однакові значення при всіх можливих значеннях пропозиційних змінних. Рівносильність формул позначається знаком º і в логіці називається законом.

Наприклад, неважко переконатися, що за довільних формул A, B, C наступні рівносильності є законами (праворуч указано назви деяких з них):

AÙB º BÙA, AÚB º BÚA – закони комутативності

AÙ(BÙC) º (AÙB)ÙC, AÚ(BÚC) º (AÚB)ÚC – закони асоціативності

AÙ(BÚC) º (AÙB)Ú(AÙC), AÚ(BÙC) º (AÚB)Ù(AÚC) – закони дистрибутивності кон'юнкції відносно диз'юнкції та диз'юнкції відносно кон'юнкції

AÙA º A, AÚA º A – закони ідемпотентності

AÚ(AÙB) º A, AÙ(AÚB) º A

Ø(AÚB) º ØAÙØB, Ø(AÙB) º ØAÚØB – закони Де Моргана

ØØA º A – закон подвійного заперечення

AÙ0 º 0, AÙ1 º A, AÚ0 º A, AÚ1 º 1 – закони поглинання

AÚØA º 1 – закон виключеного третього

AÙØA º 0 – закон суперечності

A®B º ØB®ØA – закон контрапозиції

Корисно також пам'ятати ще два закони:

(12) A®B º ØAÚB

(13) A«B º (A®B)Ù(B®A).

На законах грунтуються так звані рівносильні перетворення формул, коли формула або її підформула заміняється на рівносильну їй. В результаті одержується формула, рівносильна початковій. Такі перетворення бувають потрібні для спрощення формул. Наприклад, формула AÚ(ØA®B) має рівносильні формули AÚ(ØØAÚB), AÚ(AÚB), (AÚA)ÚB, AÚB, що одержуються послідовним застосуванням законів (12), (7), (2), (4).

3. Нормальні форми висловлень

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

Закони (2) стверджують асоціативність зв'язок кон'юнкції. Звідси формула вигляду ((…((A1ÙA2)ÙA3)Ù…)ÙAn) має еквівалентний запис A1ÙA2ÙA3Ù…ÙAn. Формула в такому записі називається кон'юнкцією формул A1, A2, A3, …, An.

Означення. Елементарною кон'юнкцією називається кон'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A1ÙØA2ÙA3.

Означення. Диз'юнктивною нормальною формою (скорочено ДНФ) називається диз'юнкція елементарних кон'юнкцій. Наприклад, формула AÙBÚBÙCÚD. Зауважимо, що її структуру краще видно в записі A×BÚB×CÚD або в записі .

Будь-яка формула може бути перетворена до ДНФ. Ми не будемо доводити це твердження, а лише опишемо потрібні рівносильні перетворення. Застосуванням законів (13) і (12) можна позбутися зв'язок « і ®, тобто перетворити формулу до рівносильної, у якій є лише зв'язки Ø, Ú і Ù. Далі, якщо у формулі є заперечення диз'юнкцій чи кон'юнкцій, то вони "спускаються" до пропозиційних змінних застосуванням законів Де Моргана (6). Далі, якщо у формулі є множники-диз'юнкції, то їх можна позбутися застосуванням першого з законів дистрибутивності (3). В результаті всі множники у кон'юнкціях формули є елементарними, і вона являє собою ДНФ. Застосування законів (1), (2), (4), (5), (7)-(10) може скоротити цей процес.

Приклад. Розглянемо перетворення (A®B)«(C®B). Після знаків º у дужках указано номери законів, застосованих при черговому перетворенні:

(A®B)«(B®C) º(13, 12)

º(Ø(ØAÚB)Ú(ØCÚB))×(Ø(ØCÚB)Ú(ØAÚB)) º(6, 7, 2)

º (A×ØBÚØCÚB)×(ØB×CÚØAÚB) º(3)