ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

Дифференциальные уравнения второго порядка (модель рынка с прогнозируемыми ценами) - В простых моделях рынка спрос и предложение обычно полагают зависящими только от текущей цены на товар.

Рівносильність та тотожність формул

На відміну від табличного задання реалізація функції формулою не єдина. Наприклад, якщо множина логічних зв’язок утворена функціями , то функцію | – "штрих Шеффера" – можна у відповідності із законами де Моргана реалізувати як або , а функцію "стрілка Пірса" як або .

Означення. Формули, які реалізують одну й ту саму булеву функцію, називаються еквивалентними або рівносильними.Рівносильність формул і

позначається .

Теорема (про основні рівносильності формул). Для будь-яких формул справедливі рівносильності:

Комутативність
1.	1^*.
Асоціативність
2.	2^*.
Дистрибутивність
відносно 3. А&(ВÚС)º(А&В)Ú(А&С)	відносно 3^*. АÚ(В&С)º(АÚВ)&(АÚС)
Закони поглинання
4.	4^*.
Закони де Моргана
5.	5^*.
Закон подвійного заперечення
6.
Закони ідемпотентності
7.	7^*.
Властивості 0 і 1
8. ;	8^*. ;
9.	9^*.
10. ,
11.
12.

Доведення (самостійно) всіх рівносильностей проводиться шляхом складання таблиць істинності для формул, що стоять в лівій і правій частинах.

Доведемо, наприклад, рівносильність 5 – закон де Моргана.

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

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

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

Означення.Рівносильним перетворенням даної формули називається заміна формули іншою формулою, їй рівносильною.

Приклад. Довести рівносильність формул

а) за допомогою таблиць;

б) шляхом рівносильних перетворень.

Розв’язання.

а)

б) .

Означення. Спрощенням формули називається рівносильне перетворення, яке приводить до формули, що містить лише символи , і , причому знак відноситься тільки до змінної.

Наступні важливі рівносильності показують, як одні елементарні булеві функції можуть бути виражені через інші, наприклад:

1) ; 5) ;

2) ; 6) ;

3) ; 7) ;

4) ; 8) .

Множина разом з кон’юнкцією, диз’юнкцією і запереченням утворює булеву алгебру – алгебру булевих функцій. Одиницею в ній є символ 1, нулем – символ 0. Оскільки за теоремою Стоуна будь-яка булева алгебра ізоморфна алгебрі підмножин множини, яка для неї підходить, то булева алгебра ізоморфна булевій алгебрі :

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

Принцип двоїстості

Звернемо увагу на характер відповідностей між рівносильностями, які наведені в теоремі про основні рівносильності формул під номерами № і №*. Ці рівносильності такі, що одна може бути отримана з іншої заміною символу операції всюди, де він зустрічається, символом операції , і навпаки. Виявляється, що це явище не є випадковим і справедливий загальний закон, що дозволяє з двох будь-яких рівносильних одна одній формул, які складені з булевих змінних за допомогою операцій , отримати формули, також рівносильні.

Означення. Логічні зв’язки і називаються двоїстими.

Означення. Нехай формула містить тільки символи . Формула називається двоїстою до формули , якщо її можна отримати з формули заміною символів , , на , відповідно.

Теорема (про двоїсту функцію).

Приклад. Побудувати формулу, двоїсту формулі

а) за означенням;

б) за теоремою про двоїсту формулу.

Розв’язання.

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

Тепер замінимо символи , , на , відповідно, отримаємо:

б) .

Теорема (про двоїстість). Якщо формули і , які містять тільки символи , рівносильні, то двоїсті до них формули також рівносильні.

Зауваження. В означенні формули символи 0 і 1 також вважаються формулами. При переході до двоїстої формули 0 замінюється 1, а 1 – 0. Наприклад, , а .

Справедливий принцип двоїстості:

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

Принцип двоїстості можна використовувати для знаходження нових рівносильностей. Наприклад, для першого закону поглинання (рівносильність 4) за принципом двоїстості маємо другий закон поглинання (рівносильність 4^*) .