1. Висловлення. Логічні операції

Висловлення – це розповідне речення, про яке можна сказати істинне воно або хибне, але не одне й інше в одночас.

Розділ логіки, який вивчає висловлення та їх властивості називається пропозиційною логікою або логікою висловлювань. Значення істиності, яке набуває будь-яке висловлення позначається 0 та 1. Висловлення позначаються латинськими літерами (А,В,С), які називають атомами. Багато речень утворюються об’єднанням кількох простих висловлень. Складні висловлення утворюються за допомогою логічних операцій: Заперечення; Кон’юнкція – лог. операція від двох аргументів p та q, яка буде істинною, коли обидва аргументи істинні. Диз’юнкція - лог. операція від двох аргументів p та q, яка буде істинною коли, хоча б один за аргументів буде істинний. Імплікація - лог. операція від двох аргументів p та q, яка буде хибною коли р – істинне, q – хибне. Еквіваленція - лог. операція від двох аргументів p та q, яка буде істинною, якщо обидва висловлення набувають однакових значень. При побудові формул розглядають два аспекти: синтаксис та семантику. Синтаксис – це сукупність правил, які дають змогу будувать формули та розпізнавати правильні формули серед послідовності символів. Формули можуть бути побудовані за такими правилами : 1) р- формула 2) р- (не)р теж формула 3) р,q-

р (диз) q, р (кон) q, р => q , р <=>q –формули

4)Формули можуть бути породжены лише скінченною кількістю застосувань данних правил. Семантика – це сукупніть правил, за якими формулам надають значення істинності. 1)Якщо р- істинне, то (не)р- хибне і навпаки. 2)Кон 3) Диз 4)Імп 5)Екв. Семантику висловлень зручно подавати за допомогою таблиць істинності.

2. Закони логіки висловлювань.

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

1) Комутативний p^q=q^p …

2) Асоціативний (р^q)^r=p^(q^r) …

3) Дистрибутивний (p^q)vr=(pvr)^(qvr) …

4) Закон де Моргана

5) Закон суперечності p^(не)р=0

6) Закон виключеного третього рv(не)р=1

7) Закон подвійного заперечення

8) Закон ідемпотентності р^q=p …

9) Закон поглинання (pvq)^p=p …

10) Співвідношення для сталих p^1=p p^0=0 p+1=1 p+0=p

3. Спеціальні форми подання булевих функцій

Спеціальними формами подання булевих функцій є кон’юктивні, диз’юктивні нормальні форми та многочлен Жегалкіна.

Елементарною кон’юнкціею називається вираз k=x₁^x₂^…^x_n , де х_і – це змінні множини х= {x_1,x_2,…,x_n }, при чому всі х_і попарно різні. Елементарну кон’юнкцію, яка містить всі змінні з множини х називають конституентою одиниці. Кількість різних конституент буде 32. ДНФ називають диз’юнкцію k₁vk₂v…vk_n елементарних кон’юнкцій у якій усі k_s попарно різні. ДДНФ називається ДНФ, у якій кожна елементарна кон’юнкція є конституентою одиниці. Т1: Будь-яку булеву функцію можна єдиним способом подати у вигляді ДДНФ.

Елементарною диз’юнкціею називається вираз d=x₁vx₂v…vx_n , де х_і – це змінні множини х= {x_1,x_2,…,x_n }, при чому всі х_і попарно різні.

Елементарну диз’юнкцію, яка містить всі змінні мнодини х називають конституентою нуля. КНФ називають кон’юнкцію D₁^D₂^…^D_n елементарних диз’юнкцій у якій усі D_s попарно різні. ДКНФ називають КНФ, у якsй кожна нормальна диз’юнкція є конституентою нуля. Т2: Будь-яку булеву функцію можна єдиним способом подати у вигляді ДКНФ.