Элементарные логические функции

Задание булевых функций посредством элементарных.

    Если в логическую функцию вместо переменных подставить некоторые булевы функции, то в результате получается новая булева функция, которая называется суперпозицией подставляемых функций, или, иными словами - сложной функцией. С помощью суперпозиции можно получать более сложные функции, которые могут зависеть от любого числа логических переменных. Запись булевых функций через элементарные булевы функции будем называть формулой реализующей данную логическую функцию.

 

Пример 1.3.1. Пусть задана элементарная булева функция x˅y. Подставим вместо x функцию x₁↓x₂. Получаем функцию трех переменных (x₁↓x₂)˅y. Если вместо переменной y подставить, например, x₃⊕x₄, то получаем новую функцию от четырех переменных: (x₁↓x₂)˅(x₃⊕x₄). Очевидно, что таким образом мы будем получать булевы функции, которые будут выражаться через элементарные булевы функции.

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

    Для более компактной записи сложных функций введем следующие соглашения: 1) внешние скобки опускаются; 2) сначала производятся операции в скобках; 3) считается, что приоритет связок убывает в следующем порядке: (инверсия), ˄ или , ˅ или +, →, ~. Для равносильных связок и оставшихся связок ⊕, |, ↓, следует пока расставлять скобки.

 

Пример 1.3.2. В формуле x˄y˅z скобки расставляются следующим образом: ((x˄y)˅z), т.к. согласно нашему соглашению операция ˄ имеет более высокий приоритет, чем операция ˅.

    В формуле x˅y~z→x скобки расставляются следующим образом: ((x˅y)~(z→x))

       В формуле (x⊕y)~z→x˄y˅z скобки расставляются следующим образом: ((x⊕y)~(z→((x˄y)˅(z)))).

    Формула x→y→z, следуя нашему соглашению, записана не корректно, т.к. расстановка скобок приводит к двум разным функциям: ((x→y)→z) и (x→(y→z)).

 

                            

Элементарные логические функции

 

  Булеву алгебру, как математическую структуру, представляют следующими объектами: 0, 1, , И, ИЛИ, НЕ, =.

Здесь 0 – символ, обозначающий ложь,

     1 - символ, обозначающий истину,

     - i - я логическая переменная, обозначающая простое высказывание,

     И – как минимум двухместная (то есть зависящая от двух переменных) логическая функция, определяемая как логическое произведение (конъюнкция). Таблица истинности логической функции И имеет вид

		И
0	0	0
0	1	0
1	0	0
1	1	1

Это означает, что это высказывание истинно только в том случае, когда истинны высказывания, от которых оно зависит, в остальных случаях оно ложно.

   Другие названия: логическое умножение (произведение); логическое «и».

Обозначения: , или , или . Читается как " икс один и икс два".

 

         

 

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

		ИЛИ
0	0	0
0	1	1
1	0	1
1	1	1

Это означает, что это высказывание ложно только в том случае, когда ложны все высказывания, от которых оно зависит, в остальных случаях оно истинно.

Обозначения: , или . Читается как " икс один или икс два".

 

       НЕ – одноместная логическая функция, определяемая как логическое отрицание (инверсия). Таблица истинности логической функции НЕ имеет вид

x	НЕ
0	1
1	0

  Обозначения:  или x. читается как "не икс" или "инверсия икс".

 

  = - отношение эквивалентности. Читается как "равно".

 

       Рассмотренные логические функции И, ИЛИ, НЕ являются элементарными булевыми функциями.

       В более общем случае булеву функцию от n переменных можно задать таблицей истинности, в которой наборы значений аргументов расположены в порядке возрастания их номеров: сначала идет набор, представляющий собой двоичное представление нуля (этот набор имеет номер 0); затем идет набор, являющийся двоичным представлением единицы, потом двойки, тройки и т.д. Последний набор состоит из n единиц и является двоичным представлением числа 2 n -1 (такой порядок расположения наборов назовем лексикографическим порядком). Учитывая, что отсчет начинается с 0, а значение булевой функции может быть либо 0 либо 1, заключаем, что существует всего различных булевых функций от n переменных. Таким образом, имеется, например, 16 булевых функций от двух переменных, 256 — от трех и т. д.

 

       Пример 1.1.1. (голосование). Рассмотрим устройство, фиксирующее принятие некоторого решения тремя собравшимися. Каждый при одобрении решения нажимает свою кнопку. Если большинство членов голосуют «за», то решение принимается. Это фиксируется регистрирующим прибором. Таким образом, устройство реализует функцию f (x,y,z), таблица истинности которой имеет вид

 

x	0	0	0	0	0	1	1	1
y	0	0	1	1	1	0	0	1
z	0	1	0	0	1	0	1	1
f (x,y,z)	0	0	0	0	1	0	1	1

       Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение 1.Полученную в примере функцию f можно также задать следующей системой равенств: f (0,0,0) = f (0,0,1) = f (0,1,0) = f (1,0,0) =0.

 

    Вектором значений булевой функции y=f(x₁,x₂,…,x_n) называется упорядоченный набор всех значений функции f, при котором значения упорядочены по лексикографическому порядку. Например, пусть функция трех переменных f задана вектором значений (0000 0010) и необходимо найти набор, на котором f принимает значение 1. Т.к. 1 стоит на 7 месте, а нумерация в лексикографическом порядке начинается с 0, то необходимо найти двоичное разложение 6. Таким образом, функция f принимает значение 1 на наборе (110).

           

 

Наряду с рассмотренными выше элементарными функциями рассмотрим несколько логических функций, которые находят широкое практическое применение.

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

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

Читается так: импликация  в  или

Другое название: логическое включение  в  .

Обозначения: → , или ⊃

 

    2. Эквивалентностью (равнозначность) называется булева функция двух переменных, которая определяется следующей таблицей истинности

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

Обозначения: , , x≡y.

  Читатается так: «икс один равнозначна икс два».

 

           

 

 

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

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

Обозначения:

 

   4. Штрих Шеффера (операция И-НЕ) - этобулева функция двух переменных, которая определяется следующей таблицей истинности

 

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

Обозначение: x|y.

   Запись x|y может читаться так: « не икс или не игрек», «икс и игрек несовместны», «икс штрих Шеффера игрек».

   5. Стрелка Пирса (операция ИЛИ-НЕ) - этобулева функция двух переменных, которая определяется следующей таблицей истинности

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

   Обозначение: x↓y.

   Запись x↓y может читаться так: «ни икс и ни игрек», «икс стрелка Пирса игрек».

 

   Замечание. Символы (инверсия), ˄ или , ˅ или +, →, ~, ⊕, |, ↓ участвующие в обозначениях элементарных функций будем называть связками или операциями.

 

Задание булевых функций посредством элементарных.

    Если в логическую функцию вместо переменных подставить некоторые булевы функции, то в результате получается новая булева функция, которая называется суперпозицией подставляемых функций, или, иными словами - сложной функцией. С помощью суперпозиции можно получать более сложные функции, которые могут зависеть от любого числа логических переменных. Запись булевых функций через элементарные булевы функции будем называть формулой реализующей данную логическую функцию.

 

Пример 1.3.1. Пусть задана элементарная булева функция x˅y. Подставим вместо x функцию x₁↓x₂. Получаем функцию трех переменных (x₁↓x₂)˅y. Если вместо переменной y подставить, например, x₃⊕x₄, то получаем новую функцию от четырех переменных: (x₁↓x₂)˅(x₃⊕x₄). Очевидно, что таким образом мы будем получать булевы функции, которые будут выражаться через элементарные булевы функции.

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

    Для более компактной записи сложных функций введем следующие соглашения: 1) внешние скобки опускаются; 2) сначала производятся операции в скобках; 3) считается, что приоритет связок убывает в следующем порядке: (инверсия), ˄ или , ˅ или +, →, ~. Для равносильных связок и оставшихся связок ⊕, |, ↓, следует пока расставлять скобки.

 

Пример 1.3.2. В формуле x˄y˅z скобки расставляются следующим образом: ((x˄y)˅z), т.к. согласно нашему соглашению операция ˄ имеет более высокий приоритет, чем операция ˅.

    В формуле x˅y~z→x скобки расставляются следующим образом: ((x˅y)~(z→x))

       В формуле (x⊕y)~z→x˄y˅z скобки расставляются следующим образом: ((x⊕y)~(z→((x˄y)˅(z)))).

    Формула x→y→z, следуя нашему соглашению, записана не корректно, т.к. расстановка скобок приводит к двум разным функциям: ((x→y)→z) и (x→(y→z)).