Материал: Diskretnaya_matematika

Функции одной переменной

Функция g₂(х) =x определяет логическую операцию –повторениепеременнойx, а функция g₃(х) =x определяет логическую операцию –отрицаниепеременнойx.

g₁(х) иg₄(х) по сути являются не функциями, а константами 0 и 1.

Функции двух переменных

f₂= х₁ х₂ – конъюнкция или логическое умножение

f₈= х₁x₂ – дизъюнкция или логическое сложение.

f₁₀ = х₁ х₂ – эквивалентность;

f₇= х₁х₂– неэквивалентность;

f₁₂= х₂х₁– функция следования (импликации) х₁;

f₁₄= х₁х₂ – функция следования (импликации) х₂;

f₃= х₁х₂ – функция запрета х₁;

f₅= х₂х₁ – функции запрета х₂;

f₉= х₁x₂– функция (стрелка) Пирса;

f₁₅= х₁| х₂ – функция (штрих) Шеффера.

Причем, функции f₂, f₈, f₁₀, f₁₂, f₁₄ определены ранее как основные логические функции (табл. 2.1).

Функции f₃, f₅, f₇, f₉, f₁₅ являются производными от них:

f₃=f₁₄или х₁х₂ = х₁ х₂,

f₅=f₁₂или х₂х₁ = х₂ х₁,

f₇=f₁₀или х₁ х₂ = х₁ х_2,

f₉=f₈или х₁x₂ = х₁ х_2.

f₁₅=f₂ или х₁| х₂ = х₁ х₂

Остальные 6 функций, по сути, не являются функциями от двух переменных. Функции f₄,f₆,f₁₁,f₁₃ зависят существенно только от одной переменной:

f₄(х₁, х₂) =  х₁, f₆(х₁, х₂) =  x₂,

f₁₁(х₁, х₂) =х₂, f₁₃(х₁, х₂) =х₁.

Функции f₁,f₁₆ не зависят ни от одной переменной и являются функциями – константами:

f₁(х₁, х₂) = 0, f₁₆(х₁, х₂) = 1.

Замечание. Операция неэквивалентности (х₁х₂), определяющая функциюf₇(х₁, х₂), имеет и другие назва­ния. В математической логике она известна еще как опера­ция «исключающее или», а в двоичной алгебре – как операция «сложение по модулю два».

Исходя из рассмотренных элементарных функций, можно построить формулы для более сложных функций трех и более числа переменных.

Пример.ФормулаF= ((х₁х₂) •х₂)х₃ определяет функцию трех переменныхf(х₁, х₂, х₃ ).

Таким образом, суперпозиция элементарных функций позволяет получить другие логические функции конечного или бесконечного числа переменных. Совокупность всех возможных логических функций образует множество, которое обозначим P₂.

2.2. Булева алгебра

2.2.1. Булевы функции и операции

Существуют много видов алгебр логики, в которых произвольная логическая функция представляется как суперпозиция некоторых базисных функций. Например, широко известной является булева система функций: конъюнкция (), дизъюнкция () и отрицание ( ). Эта система функций в качестве базиса была введена английским математиком Булем, с именем которого связа­но начало всей математической логики. Поэтому алгебра логики на основе этих операций называется алгеброй Буля илибулевой алгеброй. Рассмотрим свойства булевых операций.

Свойства булевых операций

1. Аксиоматические свойства

х • х = х, x  x = x,

x •x = 0, x x = 1, х • 0 = 0, x  0 = x,

x • 1 = x, x  1 = 1.

2. Свойства коммутативности

х₁  х₂ = х₂  х₁,

х₁ • х₂ = х₂ • х₁.

3. Свойства ассоциативности

(х₁  х₂)  х₃ = х₁  (х₂  х₃),

(х₁ • х₂) • х₃ = х₁ • (х₂ • х₃).

4. Свойства дистрибутивности

(х₁  х₂) • х₃ = (х₁ • х₃)  (х₂ • х₃),

(х₁ • х₂)  х₃ = (х₁  х₃) • (х₂  х₃).

5. Принцип двойственности (Закон де Моргана)

х₁ • х₂ = х₁ х₂,

х₁  х₂ = х₁ •х₂.

6. Закон двойного отрицания: х =х.

В булевой алгебре любая логическая функция может быть представлена булевой формулой в виде совершенной дизъюнктивной формы (СДНФ). Причем, как будет показано ниже, представление произвольной логической функции в виде СДНФ является единственным.

2.2.2. Совершенные дизъюнктивная и конъюнктивная нормальные формы

Рассмотрим возможность представления произвольной функции в виде булевой формулы, содержащей только операции дизъюнкции, конъюнкции и отрицания.

Теоремы 1 и 2 доказывают возможность такого представления. Введем некоторые понятия.

Элементарной конъюнкцией (ЭК) называется выражение где все – различны, аr–ранг конъюнкции. Функция-константа единица (U_i= 1) считается конъюнкцией нулевого ран­га.

Элементарной дизъюнкцией (ЭД) называется выражение где все – различны, а r – ранг дизъюнкции. Функция-константа единица (U_i = 0) считается дизъюнкцией нулевого ран­га.

Дизъюнктивной нормальной формой(ДНФ) называется дизъюнкция N =U₁ U₂ ...U_kэлементарных конъюнкцийU₁,U₂, ...,U_k. Совершенная ДНФ – частный случай ДНФ, элементарные конъюнкции которой содержат все переменные и ранг их равенn.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция N = U₁  U₂  ... U_k элементарных дизъюнкций U₁, U₂, ..., U_k. Совершенная КНФ – частный случай КНФ, элементарные дизъюнкции которой содержат все переменные и ранг их равен n.

Теорема 1. Произвольную логическую функцию f(х₁, х₂, ..., х_n) можно представить в виде

(2)

где σ_i  {0, 1}, x_i⁰ =х_i, x_i¹ = x_i, σ = (σ₁, …, σ_n) и дизъюнкция берётся по всем n-мерным наборам из нулей и единиц.

Доказательство. Покажем, что левая и правая части соотно­шения (2) совпадают. Подставим в (2) произвольный набор α = (α₁, …, α_n), где каждое α_i  {0,1}. В левой части по­лучим f(α₁, α₂, …, α_n), а в правой части:

Равенства в правой части вытекают из свойств конъюнкции, дизъ­юнкции и из того, что: х^σ = 1  х = σ.

Если f(х₁, х₂,..., х_n)≢0, то соотношение (2) можно перепи­сать в форме:

(3)

Эта формула (3) называется совершенной дизъюнктивной нормаль­ной формой (СДНФ) функции f(x₁, х₂,..., x_n).

Следствие. Для произвольной логической функции существует взаимнооднозначное соответствие между ее СДНФ и таблицей истинности:

а) СДНФ содержит ровно столько элементарных конъюнкций, сколько единичных наборов у функции;

б) каждому единичному набору σ = (σ₁, …, σ_n) соответствует элементарная конъюнкция всех переменных функции, в которой для σ_i= 0 переменная х_i берется с отрицанием и для σ_i= 1 – без отрицания.

Рассмотрим построение СДНФ по таблице истинности функ­ции f(x₁, х₂, ...,x_n). Для каждого набора σ = (σ₁, …, σ_n) из единичного множества [1] (такого, чтоf(σ₁, …, σ_n) = 1), составляется выражение ЭК: . Затем эти конъюнкции соединяются знаком дизъ­юнкции.

Пример 1. Построим СДНФ для функции неэкви­ва­лентности f₇(x₁, х₂)=(х₁  х₂). Исходя из единичного мно­жест­ва этой функции [1] = {(0, 1), (1, 0)} формула СДНФ будет иметь вид: F_СДНФ = х₁ • х₂  х₁•х₂.

Теорема 2. Произвольную логическую функцию f (х₁, х₂,..., х_n) можно представить в виде:

(4)

где σ_i  {0, 1}, х_i⁰ = х_i, x_i¹ = x_i, σ = (σ₁, …, σ_n)

и конъюнкция берётся по всем n-мерным наборам из нулей и единиц.

Доказательство. Из свойства булевой функции имеем f (х₁, х₂,..., х_n) = (х₁, х₂, ..., х_n). Для функции f(х₁, х₂,..., х_n) по теореме 1 существует представление в виде

тогда имеем:

что следует из закона де Моргана.

Заметим также, что . Следовательно,