Выяснить какие переменные являются существенными а какие фиктивными онлайн

Существенные и фиктивные переменные

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

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

В алгебре логики логические операции часто описываются при помощи так называемых таблиц истинности.

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

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

Определение Две функции равны, если совпадают их таблицы истинности (на объединенном наборе переменных).

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

Функций от одной переменной четыре: это константа 0, константа 1,тождественная функция, т.е. функция, значение которой совпадает с аргументом и так называемая функция «отрицание». Отрицание будем обозначать символом¬как унарную операцию. Приведём таблицы этих четырёх функций

Перенумеруем функции (их 4) и естественным образом и расположим в виде таблицы:

Видно, что f₀ (х) = 0, a f₃ (х) =1, т. е. эти две функции не зависят от х, f₁ (х) = х, т. е. она не меняет аргумента.

Функция f₂ (х) действительно содержательная функция. Она принимает значения, противоположные значениям аргумента, обозначается f₂ (х)=и называется отрицанием (читается “неx”)).

Набор значений переменных, на котором функция принимает значение f = 1, называетсяединичным набором функцииf.Аналогично набор значений, на которомf = 0, называетсянулевым набором функции f, В общем случае таблица истинности для функции отп переменных должна иметь 2 n строк.

Множество всех логических функций одной переменной – унарные логические операции– представлено в таблице 2. Число функцийР₂(1)==4.

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

Множество всех логических функций двух переменных – бинарные логические операции– представлено в таблице . Число функцийР₂(2)==16

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

Перенумеруем и расположим их тоже в естественном порядке.

1-2. Константы f₀ = 0 и f₁₅ = 1 являются константами.

Функции

являются по существу функциями одной переменной.

Операция ОТРИЦАНИЕ — «логическое не» — истинное высказывание превращает в ложное и наоборот.

Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

7) конъюнкция (функция И)

Заметим, что конъюнкция – это фактически обычное умножение (нулей и единиц). Иногда эту функцию обозначают x&y или xy;

Определение Конъюнкциейnпеременных f (x₁, x₂, …,x_n) = x₁ x₂…x_n называется функция, которая принимает значение 1, если и только если все переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0).

Конъюнкция двух высказываний истинна тогда и только тогда, когда истинны оба высказывания.

Операцию КОН’ЮНКЦИЯ называют еще «логическим и».

8) дизъюнкция (функция или)

Определение Дизъюнкциейnпеременных f (x₁,x₂, …, x_n) =x_1Ú x_2Ú … Úx_nназывается такая функция, которая равна 0 если и только если все переменные равны 0 (и, значит, равна 1 тогда и только тогда, когда хотя бы одна переменная равна 1).

Операцию ДИЗ’ЮНКЦИЯ называют еще «логическим или». Если два высказывания соединить диз’юнкцией, то получится сложное высказывание которое истинно, если истинно хотя бы одно из входящих в него высказываний.

Например, «Мы любим пиво или мы любим мороженое» истинное сложное высказывание, поскольку хотя бы одно из входящих в него элементарных высказываний истинно. А возможно,и оба.

Дизъюнкция двух высказываний ложна тогда и только тогда, когда ложны оба высказывания.

9-12) импликация (следование)

Иногда импликацию обозначают x  y (читается “из x следует y”).

операция — это ИМПЛИКАЦИЯ или «логическое если. , то».

Например, «Если Наполеон родился в Кудымкаре, то газ при нагревании сужается». Это, кстати, истинное высказывание! Нет причин считать его ложным.

Единственная ситуация, когда импликация ложна, это когда посылка (часть

«если») истинна, а следствие (часть «то») ложна.

Импликацию иногда (не совсем корректно по иным причинам!) называют операцией логического следования, хотя наш пример показывает, что высказывания могут логически не следовать одно из другого, более того, могут не иметь между собой никакой логической связи. Напомним, импликация, как и другие операции,

берет в расчет только истинность входящих в нее высказываний.

«Если Волга впадает в Каспийское море, то 2 + 2 = 4» истинное высказывание.

«Если Волга впадает в Каспийское море, то 2 + 2 = 5» ложное высказывание.

Хотя оба эти «логические рассуждения» с точки зрения здравого рассуждения одинаково бессмысленны

То есть с точки зрения формальной логики равносильны высказывания:

«ЕСЛИ стоит хорошая погода, ТО мы купаемся» и

«НЕВЕРНО, что стоит хорошая погода, ИЛИ мы купаемся».

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

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

ИЗ ИСТИНЫ НЕ МОЖЕТ СЛЕДОВАТЬ ЛОЖЬ

Это очень важная функция, особенно в логике. Ее можно рассматривать следующим образом: если х = 0 (т. е. х “ложно”), то из этого факта можно вывести и “ложь”, и “истину” (и это будет правильно), если у = 1 (т. е. у “истинно”), то истина выводится и из “лжи” и из “истины”, и это тоже правильно. Только вывод “из истины ложь” является неверным. Заметим, что любая теорема всегда фактически содержит эту логическую функцию;

13) сложение по модулю 2 (здесь и далее, если не оговорено противное, знаком “+” мы будем обозначать такое сложение):

14) эквивалентность или подобие

Есть также ЛОГИЧЕСКАЯ ЭКВИВАЛЕНТНОСТЬ или «тогда и только тогда» Результирующее сложное высказывание истинно, если одновременно истинны или ложны оба входящих в него высказывания.

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

Эта f₉ = 1 тогда и только тогда, когда х = у.

15) штрих Шеффера

Иногда эту функцию называют “не и” (так как она равна отрицанию конъюнкции);

ШТРИХ ШЕФФЕРА или логическое «и-не». Результат этой операции равносилен последовательному применению операций кон’юнкции и отрицания. Соответственно, результирующее высказывание будет ложным, только если входящие в него высказывания одновременно истинны.

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

ЗамечаниеПри использовании логики для проектирования логических схем, например отдельных фрагментов процессора, первоначально эксплуатировали аналогию с релейными схемами. Операция диз’юнкции («или») соответствует параллельному подключению контактов реле, кон’юнкции («и») — последовательному. Операция отрицания («не») моделируется нормально замкнутым контактом реле.

То есть контакт размыкается при срабатывании реле. Тогда достаточно было выпустить, например, модули типа «и-не», чтобы на них реализовать любую схему.

16) стрелка Пирса (иногда эту функцию называют штрих Лукасевича)

Эта функция является отрицанием дизъюнкции и поэтому иногда ее называют “не или”.

Три оставшиеся функции, (f₂ , f₄ и f₁₁) запрет имликации и импликация особого значения в дискретной математике не имеют.

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

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

Пример.Cоставить таблицу истинности функции трех переменных, заданной формулой:f(х₁,х₂,х₃)=()(x₁&x₃).

Для построения таблицы истинности fвычислим ее значения на каждом из восьми наборов значений .

Свойства конъюнкции, дизъюнкции и отрицания

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

Для иллюстрации коммутативного закона воспользуемся примером

«Мэри вышла замуж И родила ребенка» равносильно с точки

зрения логики тому что «Мэри родила ребенка И вышла замуж».

Перестановка не соответствует общепринятой морали — для приличного общества существенно, какое событие стоит первым. (Это в очередной раз говорит о том, что

математическая логика не учитывает [и не в состоянии это сделать!] многих нюансов, имеющих место в практике жизни).

Законы булевой алгебры

Универсальные границы:

x1 = 1; x0 =х;х1 =х;х0 = 0.

3. Ассоциативность конъюнкции и дизъюнкции:

x(yz) = (xy)z;x (y z) = (x y)z.

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

Ассоциативный закон утверждает, что безразлично, в каком порядке мы рассматриваем (истинность) попарных кон’юнкций и диз’юнкций:

«Стоит хорошая погода И мы купаемся И заработали ангину».

«Стоит хорошая погода ИЛИ мы купаемся ИЛИ заработали ангину».

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

4. Поглощение(“целое поглощает часть”):

х ху=х(1у) =х.

5. Два распределительных закона:

х (y z) =x y  x z;х (y z) = (x y)(x z),

6. Правила де Моргана:

или обобщая

Следующие 3 правила доказываются на основе законов дистрибутивности, противоречия и «исключенного третьего».

13. Поглощение ( элиминация ) :

14. Закон Блейка-Порецкого :

15. Склеивание ( объединение ) :

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

Булевы функции

Переменная Х_i называется существенной переменной функции f, если существует хотя бы одна пара u, v наборов значений переменных соседних по i — той переменной, такая, что f(u)?f(v).

Переменная Х_i называется фиктивной переменной функции f, если для любых наборов u, v соседних по i — той переменной f(u)=f(v).

Суперпозицией функций f₁, f₂, …, f_n называется функция, полученная с помощью подстановок этих функций друг в друга на места переменных, а также с помощью переименования переменных. Выражение, описывающее суперпозицию называется формулой.

Для булевой функции, заданной вектором значений (10100110), определить: 1) существенные и фиктивные переменные; 2)

Для булевой функции, заданной вектором значений (10100110), определить: 1) существенные и фиктивные переменные; 2) совершенную дизъюнктивную нормальную форму; 3) совершенную конъюнктивную нормальную форму; 4) полином Жегалкина двумя способами; 5) принадлежность классам T0,T1, S, M, L Дано: функция f(x, y,z)=(10100110) Найти. 1) существенные и фиктивные переменные; 2) совершенную дизъюнктивную нормальную форму; 3) совершенную конъюнктивную нормальную форму; 4) полином Жегалкина двумя способами; 5) принадлежность классам T0,T1, S, M, L

Для определения существенных и фиктивных переменных построим таблицу истинности для данной функции:
x y z f (x, y, z)
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
Из таблицы истинности видно, что переменная x – является существенной переменной, так как выполняется условие:
f (0, y, z) ≠ f (1, y, z).
Исследуем переменную y: f (x, 0, z) ≠ f (x, 1, z), то есть значения функции при y=0 и y=1 также не совпадают, тогда y- существенная переменная.
Исследуем переменную z: f (x, y, 0) ≠ f (x, y, 1), то есть значения функции при z=0 и z=1 также не совпадают, тогда z- существенная переменная. Фиктивных переменных нет.
Используя таблицу истинности, найдем наборы, на которых функция принимает истинные значения:
<0,0,0>, <0,1,0>, <1,0,1>, <1,1,0>Этим наборам поставим в соответствие элементарные конъюнкции по всем переменным. Переменная со значением ноль будет записана со знаком отрицания:
Получим:
<0,0,0>⟶x y z
<0,1,0>⟶x y z
<1,0,1>⟶x y z
<1,1,0>⟶x y z Эти конъюнкции объединим с помощью дизъюнкции:
x y z ⋁x y z ⋁x y z ⋁ x y z -Это Совершенная дизъюнктивная нормальная форма для данной функции.
3) Используя таблицу истинности, найдем наборы, на которых функция принимает ложные значения:
<0,0,1>, <0,1,1>, <1,0,0>, <1,1,1>Этим наборам поставим в соответствие элементарные дизъюнкции

. Переменная, которая принимает значение 1 будет записана с отрицанием:
Получим
<0,0,1>⟶x⋁ y ⋁z
<0,1,1>⟶x⋁ y⋁ z
<1,0,0>⟶x ⋁y ⋁z
<1,1,1>⟶ x ⋁y ⋁z Объединим дизъюнкции с помощью конъюнкции:
(x⋁ y ⋁z) ⋀ (x⋁ y⋁ z)⋀( x ⋁y ⋁z)⋀(x ⋁y ⋁z) -Это совершенная конъюктивная нормальная форма для данной функции.
4)Используя таблицу истинности, построим полином Жегалкина методом треугольника:
1.Строим полную таблицу истинности, в которой строки идут в порядке возрастания двоичных кодов от 000…00 до 111…11
2.Строим вспомогательную треугольную таблицу, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.
Строим таблицу истинности:
x y z f (x, y, z)
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
Строим вспомогательную таблицу:
000 001 010 011 100 101 110 111
1 z y yz x xz xy xyz
1 1 0 0 1 0 1 0
0 1 0 1 1 1 1
1 1 1 0 0 0
0 0 1 0 0
0 1 1 0
1 0 1
1 1
0
Выделим единицы, стоящие в верхних столбцах, и получим:
1+x+z+xy – Полином Жегалкина.
Построим полином Жегалкина методом неопределённых коэффициентов:
Для этого
Запишем данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами:
f(x,y,z) = a000 +a100x +a010y + a001z + a110x y + a101x z +a011y z + a111x y z
(0,0,0) = a000 = 1 ⇒ a000 = 1
f(1,0,0) = a000 + a100 = 1 + a100 = 0 ⇒ a100 = 1
f(0,1,0) = a000 + a010 = 1 + a010 = 1 ⇒ a010 = 0
f(0,0,1) = a000 + a001 = 1 + a001 = 0 ⇒ a001 = 1
f(1,1,0) = a000 + a100 + a010 +a110 = 1 + 1 + 0 + a110 = 1 ⇒ a110 = 1
f(1,0,1) = a000 + a100 + a001 + a101 = 1 + 1 + 1 + a101 = 1 ⇒ a101 = 0
f(0,1,1) = a000 + a010 + a001 + a011 = 1 + 0 + 1 + a011 = 0 ⇒ a011 = 0
Далее вычислим полученные значения, поставив в функцию.
f(1,1,1) = a000 + a100 + a010 + a001 + a110 + a101 + a011 + a111 = 1 +1 + 0 +1 +1+ 0 +0 +a111 = 0 ⇒ a111 = 0
Выбираем значения с единицей, тогда получим полином Жегалкина:
a000 = 1, a100 = 1, a001 = 1, a110 = 1 то есть
1+x+z+xy
5) Определим принадлежность функции к классам:
1

© Библиотека Ирины Эланс

Библиотека Ирины Эланс, основана как общедоступная библиотека в интернете. Онлайн-библиотеке академических ресурсов от Ирины Эланс доверяют студенты со всей России.

Библиотека Ирины Эланс

Полное или частичное копирование материалов разрешается только с указанием активной ссылки на сайт:

07. Булевы функции

P Логической, Или Булевой, переменной называется переменная, принимающая одно из двух значений 0 и 1, которые интерпретируются как «ложь» и «истина» соответственно.

P Булевой функцией называется функция N булевых переменных, принимающая одно из двух значений 0 и 1, которые интерпретируются как «ложь» и «истина» соответственно.

Булевы функции задаются таблицами истинности или логическими формулами.

Например, булева функция, заданная формулой , задаётся следующей таблицей истинности:

Переменная (I = 1, …, N) булевой функции называется Существенной, если найдутся такие наборы значений переменных и , при которых выполняется условие

.

В противном случае переменная называется Фиктивной.

Пример. Определить существенные переменные булевой функции .

Решение. Составим таблицу истинности данной функции:

Переменная Х3 является существенной для данной булевой функции, так как . Переменная является фиктивной, так как , , , . Переменная также является фиктивной, так как , , , .□

Теорема 1.6. Булеву функцию всегда можно задать формулой, не содержащей фиктивных переменных.

Например, Применим равносильности теоремы 1.1 (см. пункт 1.3) для преобразования булевой функции рассмотренного выше примера:

.

Задачи и упражнения

1.29. Приведите пример булевой функции четырёх переменных.

1.30. Постройте булеву функцию, отражающую работу устройства, состоящего из трёх узлов. Устройство пропускает сигнал, если его пропускает большинство узлов этого устройства.

1.31. Найдите существенные переменные булевой функции

.

1.32. Найдите фиктивные переменные булевой функции

.

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