Теорема 1 Теорема про проходження та імплікацію

(Тут і далі символ відповідатиме словесному формулюванню «тоді й тільки тоді»)

Необхідність:

т.к. , ,

або ,

Достатність:

Значить,

Узагальнення теореми 1:

Г, Г, де Г =

Слідство:

Рівносильність

Рівносильність формули У формулі А позначатимемо:

Формула А рівносильна формулі В, якщо у будь-якій інтерпретації I. У разі логіки висловлювань формули рівносильні, якщо їх таблиці істинності однакові, що використовується для доказу рівносильності.

Основні формули рівносильності

1) - ідемпотентність

2) , – комутативність

3) - асоціативність

4) - дистрибутивність

5) Закони де Моргана

Для алгебри предикатів необхідно додати закон комутативності для кванторів

та закони де Моргана для кванторів

Відношення рівносильності пов'язане зі ставленням слідування

Теорема 2:

Необхідність:

Достатність: у зворотний бік

Теорема 3: пов'язує відношення рівносильності з операцією еквівалентності

Слідство:

Теорема 4: Теорема про еквівалентну заміну

Якщо і є C, яке A входить в якості підформули,

CB – формула, де всі входження формули А замінені на формулу У.

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

Бульові функції та нормальні форми

Логічними функціями називаються функції від булевих змінних, значення яких - булеве значення.

B n B

2.1 Способи завдання

Завдання логічної функції за допомогоютаблиці

Кожна логічна функція М.Б. задана за допомогою таблиці.

Приклад: Задана деяка булева функція.

X

Y

Z

F(x, y, z)

Усього 2 n логічних наборів змінних.

Скільки м.б. різних булевих функцій від n змінних?

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

Таким чином, при n=1 отримуємо 2 2 =4 лог. функцій f(x).

x

x

При n=2 отримуємо 16 функцій.

x

y

(x)

(y)

x

y

(x) – константа х (y) – константа y

x - заперечення хy - заперечення y

Константа 0 1 - константа 1

- кон'юнкція – Диз'юнкція

- Імплікація – еквівалентність

- порівняння x>y - порівняння x ,→), (

:

При нульових значеннях аргументу, мають значення-нуль.

2) F1 – функції, що зберігають «1».

У разі, коли всі значення аргументу = 1, значення функції = 1.

3) F 2 - монотонні функції.

n-місцева логічна функція належить класу монотонних функцій, якщо ми маємо 2 набори , причому , а це означає, що тоді значення .

Тобто. якщо набір збільшується, значення функцій також має збільшуватися, тому монотонна функція.

4) F 3 – лінійні функції.

де C0 …. Cn – є булевими константами (0 або 1).

5) F 4-самодвійні функції.

Подвійною функцією називається функція виду:

Самодвійною функцією називається функція подвійна сама собі.

Теорема Посту.

Є багато функцій. Багато функцій є повним, якщо можна висловити всі інші функції через функції цієї множини.

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

Нормальні форми

---