Способы задания булевых функций.

Способы задания не отличаются от обычных способов задания функций в анализе.

1. Табличный.

2. Графический.

3. Аналитический.

Табличный способ задания.

Пусть w = f(x₁, x₂, ..., x_n) - булева функция от n переменных, Область определения можно рассматривать как множество упорядоченных наборов D = {x₁, x₂, ..., x_n | x_i {0, 1}, i = 1, 2, ..., n}, на каждом из которых функция принимает одно из двух значений w = {0, 1}. Количество таких наборов {x₁, x₂, ..., x_n} согласно правилу прямого произведения равно

Нетрудно определить и количество всех функций w = f(x₁, x₂, ..., x_n) .Отдельная функция w = f(x₁, x₂, ..., x_n) задана, если заданы значения {w₁, w₂, ... w_n} на всех значениях {x₁, x₂, ..., x_n} D, где w_j = {0, 1}- значение функции на j – том наборе { x₁, x₂, ..., x_n}. Таких наборов 2ⁿ. Отсюда,

В частности, существуют четыре булевы функции одной переменной.

x f₀(x) = 0 f₁(x) =

0 0 0 1 1

1 0 1 0 1

Функции f₀(x), f₁(x), f₃(x) называются соответственно нулем, отрицаниям, единицей.

Имеется 16 булевых функций двух переменных

0 0 0 0 0 0 0 0 0 0

0 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1

0 0 1 1 1 1 1 1 1 1

0 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1

Названия функций: f₁ – конъюнкция, f₆ – сложение по модулю 2 ( не эквивалентно), f₇ – дизъюнкция, f₈ – стрелка Пирса, f₉ – эквивалентность или эквиваленция, f₁₃ – импликация, f₁₄ – штрих Шеффера.

В таблице обычно употребляется расположение наборов, соответствующих порядку естественного роста двоичных чисел 0, 1, …, 2ⁿ – 1.

Определение. Таблицы, подобные рассмотренным, называются таблицами истинности булевых функций.

Графический способ задания.

Графически область определения функции функция w = f(x₁, x₂, ..., x_n) представляется в виде точек, являющихся вершинами единичного n – мерного куба. Например, для w = f(x, y, z)

z Чтобы задать функцию, надо отметить точки, которых

0,0,1 0,1,1 значение функции равно 1.

1,0,1 1,1,1

y

1 ,0,0 1,1.0

x

Например, для функции f(x₁, x₂, x₃) ≡ имеем

f(1, 0, 0) = f(1, 0, 1) = f(1, 1, 1) = 1.

Аналитический способ задания.

В таблице истинности, рассмотренных ранее, приведены элементарные функции одного и двух переменных

Логика предикатов. Кванторы.

Рассмотрим ряд высказываний: «1 есть простое число», «2 есть простое число», «3 есть простое число»;«4 есть простое число» и т.д. Одни из этих высказываний истинны, другие – ложны, но все они получаются из выражения «n есть простое число», если вместо n подставлять те или иные натуральные числа. Обозначим это выражение через P(n). Само P(n) не является высказыванием, т. к. нельзя сказать истинно оно или ложно, но оно превращается в высказывание при каждом n N. Выражение такого типа называется одноместным предикатом, определенным на множестве N.

Аналогично, примером двухместного предиката является выражение «x дружит с y», где x и y принадлежат , например, множеству студентов второго курса..

Определение. Пусть x₁, x₂, ..., x_n - символы переменных произвольной природы. Эти переменные будем называть предметными. Пусть наборы переменных (x₁, x₂, ..., x_n) принадлежат некоторому множеству Ω, которое будем называть предметной областью. Тогда n – местным предикатом, определенным на предметной области Ω , называется отображение Ω во множество высказываний.

Квазиопределение. Связное повествовательное предложение, содержащее n переменных и обладающее следующим свойством: при фиксации значений всех переменных о предложении можно сказать истинно оно или ложно.

Для n – местного предиката существует обозначение P(x₁, x₂, ..., x_n ), где P - имя предиката.

Определение. Характеристической функцией предиката P(x₁, x₂, ..., x_n), определенного на предметной области Ω, называется

П р и м е р 1 .Пусть Ω = {2, 3, ..., 8}. Р(x) означает «х – простое число». Таблица истинности этого предиката имеет вид

x P(x)

2 1

3 1

4 0

5 1

6 0

7 1

8 0

П р и м е р 2. Пусть Ω = {1, 2, 3, 4}² и P(x, y) означает «х является делителем у». Тогда этот предикат можно задать матрицей смежности, которая является фактически таблицей истинности, записанной в более удобном виде

x y

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

Если характеристическая функция предиката тождественно равна нулю, то такой предикат называется тождественно ложным.

Пример тождественно истинного предиката: .

Пример тождественно ложного предиката: .

Все операции над высказываниями имеют смысл и для предикатов. Но имеются две важные логические операции, которые имеют именно для предикатов.

Пусть P(x) – одноместный предикат, определенный на области Ω. Поставим ему в соответствие высказывание: «для каждого х Ω Р(х) – истинно». Такое высказывание обозначается и читается «для каждого х имеет место P(x)». Это высказывание истинно тогда и только тогда, когда Р(х) – тождественно истинный предикат.

Определение. Значок называется квантором всеобщности. Говорят, что высказывание получается из предиката Р(х) навешиванием квантора всеобщности.

Составим еще одно высказывание о предикате Р(х) «существует х Ω, для которого Р(х) истинно».Такое высказывание обозначается и читается «существует x, для которого имеет место Р(х). Это высказывание ложно тогда и только тогда, когда Р(х) тождественно ложный предикат.

Определение. Значок называется квантором существования. Говорят, что высказывание получается из предиката Р(х) навешиванием квантора существования.

Обозначения и для кванторов – это перевернутые латинские буквы А и Е, которые являются первыми буквами английских слов «All» и «Exist».

Если предметная область Ω конечна Ω ={a₁, a₂, ..., a_k}, то высказывание равносильно конъюнкции

При этом справедливы обобщенные законы де Моргана

П р и м е р . Ω = N², а Р(х, у) означает «х является делителем у», тогда

На языке предикатов можно записать многие математические понятия.

Например. Пусть a является пределом последовательности {x_n}. Это означает:

каково бы ни было ε, найдется такое натуральное число N. что для всех n > N выполняется соотношение |x_n – a| < ε. Это высказывание. Существование предела равно истинности этого высказывания. Итак.