• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

ІІ. Алгебра висловлень

2. Означення логічних операцій

Основними об’єктами алгебри висловлень є елементарні висловлення. Кожне елементарне висловлення обов’язково повинно бути або істинним, або хибним. Будемо позначати елементарні висловлення малими латинськими буквами a, b, c, …, x, y, z,… Значення істинності позначають буквою І або цифрою 1, значення хибності – Х або 0.

Приклади елементарних висловлень: 2 > 3, 2 × 2 = 4, „ сніг білий ”, „ парта чорна ”. Елементарним висловленням відповідають прості речення української мови, в яких щось стверджується. Складні речення містять сполучники і є прикладами складних висловлень.

Сполучникам „і”, „або”, „якщо..., то...”, слову „еквівалентно” та частці „не” в алгебрі висловлень відповідають логічні операції „кон’юнкція”, „диз’юнкція”, „імплікація”, „еквівалентність” та „заперечення”. Позначають ці операції символами:

Ù , Ú , ", 1 , ¯ .

Дамо означення логічних операцій:

0 0 0 1 1 0 1 1

Відмітимо ще:

- „кон’юнкція”, „логічне множення”, читають: „x і y”.

- „диз’юнкція”, „логічне додавання”, читають: „x або y”, “або” в нероздільному розумінні.

- „імплікація”, „логічне слідування”, читають: „якщо x, то y”, „з х слідує (випливає) у”.

- „еквівалентність”, читають: „x еквівалентно y”.

¯ - заперечення, читають: „не x”

3.Формули алгебри висловлень

Кожна буква, що виражає елементарне висловлення, є формулою. З букв за допомогою логічних операцій можна будувати нові формули. Зв’язуючи побудовані формули знаками логічних операцій, одержуватимемо нові, більш складні формули. Формули з двох або більшої кількості букв виражають складні висловлення. При цих побудовах формули з двох або більшої кількості букв потрібно брати в дужки. Приклади:

ab, bc, ab, …, , , …

, ,…

Можна обчислити значення істинності висловлення для деякого набору значень елементарних висловлень. Наприклад:

|₀₁₀ ===, .

Визначимо порядок старшинства операцій: ¯ , , , , . Домовимось, що

=. Будемо використовувати це для спрощення запису формул. Наприклад:

= =.

Побудуємо таблицю істинності висловлення, що виражається формулою .

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Побудована таблиця дає нам значення істинності складного висловлення, що виражається формулою для всіх можливих наборів значень елементарних висловлень , , . З іншого боку, формула і таблиця виражають деяку функцію від трьох змінних , , . Особливість цієї функції полягає в тому, що значення функції та Ії аргументів належать множині {0,1}. Такі функції називають бульовими.

4. Бульові функціхї та їх властивості

Означення. Функцію f(x₁,x₂,…x_n), для якої f,x₁,x₂,…x_n{0;1} називають n-місною бульовою функцією.

Властивість 1. n-місна Бульова функція визначена на 2ⁿ наборах.

Доведення. Побудуємо таблицю наборів для довільної n-місної бульової функції. Набори значень аргументів розташовуємо в порядку зростання двійкового числа. У першому рядку

x1 x2 ... xn-1 xn
0 0 … 0 0 0 0 … 0 1 0 0 … 1 0 ……………...... 1 1 … 1 0 1 1 … 1 1

записано число 0, в другому – число 1, в третьому – число 2 і т.д. В останньому рядку записано двійкове число, що виражає кількість наборів, починаючи з другого. Додаючи число 1 до двійкового числа, що записано в останньому наборі, одержуємо кількість всіх наборів, записану двійковим числом. Залишається перевести число з двійкової системи числення в десяткову. Позначаючи кількість всіх наборів буквою m, маємо:

m = 11…11₂ + 1 = 100…00₂ = 1×2ⁿ+ 0×2^n-1 + 0×2^n-2 + … + 0×2¹ + 0×2 ⁰ = 2ⁿ

Запишемо одержаний результат у формі властивості двійкових чисел:

Різних двійкових чисел, розмірність яких не перевищує n, Існує точно 2ⁿ.

Властивість 2. Різних n-місних бульових функцій існує точно .

Доведення. Побудуємо таблицю значень всіх можливих n - місних бульових функцій від f₁ до f _k.

x1 x2 ... xn-1 xn				………………
0 0 … 0 0 0 0 … 0 1 0 0 … 1 0 …………….. 1 1 … 1 0 1 1 … 1 1	…	...	...	..................... ......................   ......................   ......................	...	...

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

k = 2^m, де m – кількість наборів. Вище доведено, що m = 2ⁿ, тому k = .

5. Рівносильні та тотожно істинні формули алгебри висловлень

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

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

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

a b			b
0 0 0 1 1 0 1 1

Значення в таблицях істинності співпадають, тому =b.

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

Приклад. Перевірити, чи тотожно істинною є формула .

a b
0 0 0 1 1 0 1 1

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

6. Огляд всіх можливих 2- місних бульових функцій

Підрахуємо кількість всіх можливих двомісних бульових функцій.

|_n=2=

Побудуємо таблицю істинності для всіх цих функцій.

Запишемо формулою кожну з побудованих функцій.

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

Функції і визначають операції кон’юнкцію і диз’юнкцію. За допомогою функцій та можна ввести ще дві логічні операції /,: = = x/ y, == xy. Ці операції використовують в техніці. Першу з них називають штрих Шеффера, а другу називають стрілка Пірса.

7. Функціонально повний набір логічних операцій

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

Теорема. Набір логічних операцій ¯ , , , , є функціонально повним .

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

Покажемо, що функціонально повний набір (ФПН) логічних операцій може містити меншу кількість операцій.

№	Ф П Н	Обґрунтування
	¯ , , , ,	Теорема про Ф П Н
	¯ , , ,
	¯ , ,
	¯ ,
	¯ ,
	/	= x/ y
		= xy

Читайте також:

1. Алгебра випадкових подій
2. Алгебра множин
3. Алгебра подій
4. Алгебраїчний спосіб визначення точки беззбитковості
5. Алгебраїчні критерії стійкості
6. Алгебраїчні операції
7. Алгебраїчні системи
8. ІІІ. Бульова алгебра
9. Мінори та алгебраїчні доповнення.
10. Однорідні системи лінійних алгебраїчних рівнянь.
11. Операція еквіваленції висловлень.

Переглядів: 4111