Iванов Є. В.
4 Булевi функцïı та вирази
Iванов Є. В.
4.1 Булевi функцïı
Булевi функцiï – це функцiï однiєï або кiлькох змiнних, значення i кожен з аргументiв яких можуть приймати лише одне з двох значень: 0 або 1. Значення 1 може трактуватися“ iстина”, а значення 0 – як“ хибнiсть”. При такiй iнтерпретацiï булавi функцiï можуть використовуватися для визначення iстинностi певного висловлювання через iстиннiсть iнших висловлювань.
Розглянемо приклад. Якщо A, B – висловлювання( речення, якi можна охарактеризувати як iстиннi або хибнi, наприклад“ число 1 менше за число 2” або“ число 1 бiльше за число 2”), то висловлювання“ A та B” є iстинним тодi i тiльки тодi, коли висловлювання A iстинне та висловлювання B iстинне. Нехай x – значення, яке рiвне 0, якщо A iстинне, або 1, якщо А хибне. Аналогiчно, нехай y – значення, яке рiвне 0, якщо B iстинне, або 1, якщо B хибне, та нехай z – значення, яке рiвне 0, якщо висловлювання“ A та B” iстинне, або 1, якщо висловлювання“ A та B” хибне. Тодi значення z можна однозначно визначити, знаючи значення x та y, а саме: – якщо x = 0 i y = 0, то z = 0; – якщо x = 0 i y = 1, то z = 0; – якщо x = 1 i y = 0, то z = 0; – якщо x = 1 i y = 1, то z = 1. Вказанi 4 випадки вичерпують всi можливi набори значень x та y, тому наведенi правила визначають функцiю вiд двох аргументiв, якi можуть приймати значення 0 або 1, яка сама може приймати значення 0 або 1. Цю функцiю називають булевою операцiєю I( кон’ юнкцiєю) i часто позначають як ∧. Таким чином, z = x ∧ y( символ операцiï ∧ ставлять мiж ïï аргументами, що являє собою iнфiксну форму запису, що характерна i для запису арифметичних операцiй). Дана операцiя має властивостi 0 ∧ 0 = 0, 0 ∧ 1 = 0, 1 ∧ 0 = 0, 1 ∧ 1 = 1. Фактично, значення x ∧ y можна виразити, застосувавши арифметичну операцiю множення: x ∧ y = x ∙ y( при x ∈ 0, 1 та y ∈ 0, 1). Проте
55