Елементи логіки

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

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

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

(1)AB  BA, AB  BA – закони комутативності

(2)A(BC)  (AB)C, A(BC)  (AB)C – закони асоціативності

(3)A(BC)  (AB)(AC), A(BC)  (AB)(AC) – закони дистрибутивності кон'юнкції відносно диз'юнкції та диз'юнкції відносно кон'юнкції

(4)AA  A, AA  A – закони ідемпотентності

(5)A(AB)  A, A(AB)  A

(6)(AB)  AB, (AB)  AB – закони Де Моргана

(7)A  A – закон подвійного заперечення

(8)A0  0, A1  A, A0  A, A1  1 – закони поглинання

(9)AA  1 – закон виключеного третього

(10)AA  0 – закон суперечності

(11)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.