Как найти количество логических функций - Исправление недочетов и поиск решений вместе с Examum.ru

In the below article, we are going to find the number of Boolean Functions possible from the given sets of binary number.

Statement-1:
Suppose two sets are set ‘A’ = {1, 2, 3, 4, …….., n} where each number will be either ‘0’ or ‘1’ and hence the total number of boolean variable possible will be and set ‘B’ = {0, 1}. Now the number of possible boolean function when counting is done from set ‘A’ to ‘B’ will be $2^{(2^n)}$ .

Explanation:
As we know that boolean variable is either ‘0’ or ‘1’ and in the set ‘A’ there are ‘n’ numbers and each number will be either ‘0’ or ‘1’ and hence the total number of possible boolean variable are . Now set ‘A’ contain boolean variable and set ‘B’ contain 2 boolean variable.

This can be understood with help of below diagram:

Each element of set ‘A’ makes a function with each element of set ‘B’ hence one element of set ‘A’ makes two function with set ‘B’ and hence total number of possible boolean functions are $2^{(2^n)}$ where is the number of element in set ‘A’.

Statement-2:
Suppose two sets of ternary variable are set ‘A’ = {1, 2, 3, 4, …….., n} where each number will be either ‘0’ or ‘1’ or ‘2’ and hence the total number of ternary variable possible will be and set ‘B’ = {0, 1}. Now the number of possible boolean function when counting is done from set ‘A’ to ‘B’ will be $2^{(3^n)}$ .

Explanation:
As we know that ternary variables are ‘0’ or ‘1’ or ‘2’ and in the set ‘A’ there are ‘n’ numbers and each number will be either ‘0’ or ‘1’ or ‘2’ and hence the total number of possible ternary variables are . Now set ‘A’ contain ternary numbers and set ‘B’ contain 2 boolean variable.

This can be understood with help of below diagram:

Each element of set ‘A’ makes a function with each element of set ‘B’ hence one element of set ‘A’ makes two functions with set ‘B’ and hence the total number of possible boolean functions are $2^{(3^n)}$ where is the number of elements in set ‘A’.

Note:

Similarly for a set ‘A’ of ‘n’ numbers of k-ary variable and set ‘B’ of p-ary variable then the total number of p-ary possible function will be $p^{(k^n)}$ .

Last Updated :
25 Nov, 2019

Like Article

Save Article

Источник

Логические функции.

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

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

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

Выясним количество логических функций для двух аргументов.

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

x	y	f₂	f₃	f₄	f₅	f₆	f₇	f₈
0	0	0	0	0	0	0	0	0
0	1	0	0	0	1	1	1	1
1	0	0	1	1	0	0	1	1
1	1	1	0	1	0	1	0	1

x	y	f₉	f₁₀	f₁₁	f₁₂	f₁₃	f₁₄	f₁₅	f₁₆
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₁(x, y) = 0 — константа «ложь»
f₂(x, y) = x ∧ y — конъюнкция
f₃(x, y) = ¬ (x ⇒ y) — отрицание импликации
f₄(x, y) = х — функция равна первому аргументу
f₅(x, y) = ¬ (y ⇒ x) — отрицание обратной импликации
f₆(x, y) = у — функция равна второму аргументу
f₇(x, y) = x ⊕ y — разделительная (строгая дизъюнкция)
f₈(x, y) = x ∨ y — дизъюнкция
f₉(x, y) = x ↓ y — стрелка Пирса
f₁₀(x, y) = x ≡ y — эквивалентность
f₁₁(x, y) = ¬ y — отрицание второго аргумента
f₁₂(x, y) = y ⇒ x — обратная импликация
f₁₃(x, y) = ¬ x — отрицание первого аргумента
f₁₄(x, y) = x ⇒ y — импликация
f₁₅(x, y) = x | y — штрих Шеффера
f₁₆(x, y) = 1 — константа «истина»

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

Источник

Логические функции, соответствующие
логическим операциям В²aВ,
называют элементарными. Количество
логических функций отnпеременных определяется выражением
2²ⁿ,
поскольку|Bⁿ|=2ⁿ,
а на каждом из2ⁿнаборов логическая функция может
принимать одно из значений из того же
множества В (табл.5.4).

Табл.5.4

№	Набор	Номер логической функции
п/п	значений переменных	0	1	2	3	…	2²ⁿ-1
1	00…00	0	1	0	1	…	1
2	00…01	0	0	1	1	…	1
3	00…10	0	0	0	0	…	1
4	00…11	0	0	0	0	…	1
. . .	. . .	. . .	. . .	. . .	. . .	…	. . .
2²	11…11	0	0	0	0		1

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

Табл.5.5

	Логическая функция
х	f₀(x)	f₁(x)	f₂(x)	f₃(x)
0	0	1	0	1
1	0	0	1	1

Поскольку
2²¹=4,
то имеется четыре логических функции
одной переменной, две из них — константы:f₀(x)=0,f₃(x)=1.f₀(x)- константа нуля,f₃(x)- константа единицы. Здесь номер функции
означает десятичное число, соответствующее
двоичному числу, записанному в первом
и последнем столбцах табл.5.5.

Функция f₁(x)=х,
т.е. совпадает со значением переменной.
Эта функция называется функцией
повторения. Функцияf₂(x)=нам уже известна — это инверсия.

Можно заметить, что для каждой функции
одной переменной существует инверсная
ей:

f₀(x)=₃(х)==1;

f₃(x)=₀(х)==0;

f₁(x)=₂(х)==х;

f₂(x)=₁(х)=.

Рассмотрим все функции двух переменных
(табл.5.6).

Табл.5.6

Вес разряда вектора
значения функции

		2⁰	2¹	2²	2³
		Набор	Название	Формула
2⁰	х₁	0	1	0	1	функции	(Вебба)
2¹	х₂	0	0	1	1
	f₀	0	0	0	0	Константа 0	0
	f₁	1	0	0	0	Функция Пирса (Вебба), «стрелка Пирса», ИЛИ-НЕ	х₁¯х₂=
	f₂	0	1	0	0	Запрет х₂	х₁
	f₃	1	1	0	0	Отрицание х₂
	f₄	0	0	1	0	Запрет х₁	х₂
	f₅	1	0	1	0	Отрицание х₁
	f₆	0	1	1	0	Сложение по mod2	х₁Åх₂= х₁Úх₂
	f₇	1	1	1	0	Функция Шеффера, «штрих Шеффера», И-НЕ	х₁\|х₂= Ú
	f₈	0	0	0	1	Конъюнкция, И	х₁х₂
	f₉	1	0	0	1	Эквиваленция (эквивалентность)	х₁«х₂= х₁х₂Ú
	f₁₀	0	1	0	1	Повторение х₁	х₁
	f₁₁	1	1	0	1	Импликация х₂в х₁	х₂®х₁ Úх₁
	f₁₂	0	0	1	1	Повторение х₂	х₂
	f₁₃	1	0	1	1	Импликация х₁в х₂	х₁®х₂ Úх₂
	f₁₄	0	1	1	1	Дизъюнкция, ИЛИ	х₁Úх₂
	f₁₅	1	1	1	1	Константа 1	f₁

Всего таких функций имеется 2²²=2⁴=16.
Согласно табл.5.6 существуют две функции
— константы 0,1, которые не зависят от
значения переменных. Есть функции,
зависящие только от одной переменной.
Такие функции называют вырожденными.
Перечислим их:

f₀(x₁x₂)=0;
f₅(x₁x₂)=;f₃(x₁x₂)=;

f₁₅(x₁x₂)=1;f₁₀(x₁x₂)=х₁;f₁₂(x₁x₂)=х₂.

Некоторые функции мы тоже уже знаем:
конъюнкцию f₈(x₁x₂)=х₁х₂(точку между х₁и
х₂опускаем); дизъюнкциюf₁₄(x₁x₂)=х₁Úх₂;
эквиваленцию (эквивалентность)f₉(x₁x₂)=х₁«х₂=х₁х₂Ú(здесь эквиваленция представлена в виде
дизъюнкции двух конъюнкций, что можно
доказать, составив таблицу истинности);
импликациюf₁₃(x₁x₂)=х₁®х₂=Úх₂;
импликациюf₁₁(x₁x₂)=х₂®х₁=Úх₁.

Кроме этого, имеются другие функции,
зависящие от двух переменных: f₁(x₁x₂)=носит название функции Пирса (Вебба)
(«стрелка Пирса»),f₇(x₁x₂)=Úносит название функции Шеффера («штрих
Шеффера»),f₂(x₁x₂)=х₁называется запретом х₂, аf₄(x₁x₂)=х₂— запретом х₁. Функцияf₆(x₁x₂)называется сложением по модулю два, это
функция, инверсная эквиваленции и
обозначается х₁Åх₂(mod2).

Элементарные логические функции
позволяют получить сложные функции от
большего числа аргументов путем
подстановки в данную функцию вместо ее
переменных других функций. Такой метод
получения функций называется суперпозицией.
Например, имея элементарные функции
двух переменных z₁=x₁x₂
иz₂=x₃Úx₄можно получить функцииz₃=х₁(x₃Úx₄),z₄=x₃Úх₁x₂,
зависящие от трех переменных.

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

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

1) Класс функций, сохраняющих константу
0. В этот класс входят функции, которые
на нулевом наборе переменных принимают
нулевое значение: f(00…0)=0.
Такова, например, конъюнкцияf₈=х₁х₂f₈(00)=0×0=0.

2) Класс функций, сохраняющих константу
1. В этот класс входят функции, которые
на единичном наборе переменных принимают
единичное значение: f(11…1)=1.
Этим свойством также обладает конъюнкцияf₈(11)=1×1=1.
Классы 1,2 легко устанавливаются по
таблице истинности.

3) Класс самодвойственных функций.
Логические функции f(х₁х₂…х_n)
иg(х₁х₂…х_n)
называются двойственными, если
имеет место равенство

f(х₁х₂…х_n)=,

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

Например, f₈(х₁х₂)=х₁х₂иf₁₄(x₁x₂)=х₁Úх₂двойственны:

Это можно доказать, построив таблицу
истинности:

Табл.5.7

х₁	х₂		х₁х₂
0	0	0	0
0	1	0	0
1	0	0	0
1	1	1	1

Логическая функция называется
самодвойственной, если она двойственна
по отношению к самой себе:

f(х₁х₂…х_n)=.

Такова, например, функция f₁₀(x₁x₂)=x₁:

Самодвойственность
устанавливается по таблице истинности
следующим образом: значения функции,
симметричные относительно середины
таблицы инверсны. Например, дляf₁₀(x₁x₂)значения функции представляют собой
вектор 01 01, каждый разряд которого
является инверсным по отношению к
симметричному разряду относительно
середины, отмеченной пунктиром. Эти
разряды соответствуют инверсным наборам
х₁х₂: 00 — 11, 01 — 10. Самодвойственны
функции,,х₂,х₁.

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

f(x₁x₂)=с₀Åс₁х₁Åс₂х₂,

где с₀,с₁,с₂— константы
0,1.

Например, для сложения по модулю 2(mod2):

f₆(x₁x₂)=х₁Åх₂.

с₀=0, с₁=с₂=1:

f₆(x₁x₂)=0Å1×х₁Å1х₂.

Получим все линейные функции двух
переменных, задав все возможные значения
с₀с₁с₂(табл.5.8).

Табл.5.8

с₀	с₁	с₂	Вид полинома
0	0	0	0	Можно доказать,
0	0	1	х₂	используя, например,
0	1	0	х₁	таблицу истинности,
0	1	1	х₁Åх₂	что:
1	0	0	1
1	0	1	1Åх₂	=
1	1	0	1Åх₁	=
1	1	1	1Åх₁Åх₂	=

Видно, что каждая линейная функция имеет
инверсную ей. Таким образом, линейные
функции — константа 0, константа 1,
повторение х₁,х₂, инверсии:,,
сложение по модулю 2 (х₁Åх₂)
и инверсная ей эквиваленция.

5) Класс монотонных функций. Монотонная
функция на большем сравнимом наборе
переменных принимает не меньшие значения.
Это удобно проверять на решетках Хассэ.
Так, для двух переменных решетка имеет
вид рис.5.1.

На рис.5.1 видно, что 11>01>00,
11>10>00(частично упорядоченное
множество наборов).

Рис.5.1. Решетка Хассэ для двух переменных

с указанием значений f₁₀(х₁х₂)=х₁

Очевидно, что константы 0,1 — монотонные
функции, дизъюнкция, и конъюнкция —
монотонные функции, повторения х₁,х₂— монотонные функции. На рис.5.1 проставлены
значения монотонной функции х₁.

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

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

— не сохраняющую константу 0;

— не сохраняющую константу 1;

— несамодвойственную;

— нелинейную;

— немонотонную.

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

Оказывается, имеются функции, обладающие
всеми пятью отмеченными свойствами.
Таковы функции f₁(x₁x₂)=иf₇(x₁x₂)=Ú.
Часто их называют соответственно ИЛИ-НЕ,
И-НЕ. Таким образом, это базисы, состоящие
из одной функции (базис Вебба и базис
Шеффера). Этот факт очень важен при
технической реализации дискретных
устройств: достаточно иметь элементы,
реализующие только одну из этих функций,
чтобы построить любую, сколь угодно
сложную схему. Более подробно этот
вопрос будет рассмотрен при изучении
синтеза автоматов.

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

Иногда используется не минимальный
базис — из трех функций:

Имеется и довольно экзотический базис
Жегалкина:

В дальнейшем нам пригодится так называемый
импликативный базис

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

Соседние файлы в папке TURIN

Источник

Логические функции

Любую логическую формулу можно рассмотреть как функцию F(x₁, x₂, …, x_n), где x₁, x₂, …, x_n – это логические переменные, которые могут принимать только значения «истина» (1) и «ложь» (0). Значение логической функции также либо «истина» (1) и «ложь» (0). Все рассмотренные ранее бинарные и унарные логические операции можно считать функциями от соответствующего числа переменных: отрицание F(x)= не x, конъюнкция F(x,y)=x & y, дизъюнкция F(x,y)=x v y, разделительная дизъюнкция F(x,y)=x Δ y, импликация F(x,y)=x → y, эквивалентность F(x,y)=x ↔ y. Однако это не все функции, которые можно построить от двух переменных x и y. Каждая логическая функция от двух переменных имеет 4 возможных набора значений аргументов, и мы можем определить, какое количество различных логических функций от двух переменных может существовать:
N = 2⁴ = 16.
Таким образом, существует 16 различных функций от двух переменных, каждая из которых может быть задана своей таблицей истинности.

Аргументы	Логические функции
x	y	F₁	F₂	F₃	F₄	F₅	F₆	F₇	F₈	F₉	F₁₀	F₁₁	F₁₂	F₁₃	F₁₄	F₁₅	F₁₆
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Так как функций от двух переменных всего 16, то в алгебре логики все эти функции имеют свои имена:

F1(x,y)=0	константа ложь
F2(x,y)=x&y	конъюнкция
F3(x,y)=не (x→y)	отрицание импликации
F4(x,y)=x	функция равна первому аргументу
F5(x,y)=не (y→x)	отрицание обратной импликации
F6(x,y)=y	функция равна второму аргументу
F7(x,y)=x Δ y	разделительная дизъюнкция
F8(x,y)=x v y	дизъюнкция
F9(x,y)=x ↓ y	стрелка Пирса(отрицание дизъюнкции)
F10(x,y)=x ↔ y	эквивалентность
F11(x,y)=не y	отрицание второго аргумента

Заметим, что одна и та же функция может выражаться различными формулами. Например, функция штрих Шеффера может быть выражена как формулой не (x & y) так и формулой не x v не y.

Для большего числа переменных также можно подсчитать количество различных функций. Для k логических переменных можно построить m = 2^k различных наборов значений, то есть любая таблица истинности функции от k переменных будет иметь 2^k строк. Поэтому количество различных функций от k переменных будет 2^m = 2^2k.

Отметим, что задаются логические функции двумя способами:
1) с помощью таблицы истинности:

x	y	f
0	0	0
0	1	0
1	0	0
1	1	1

2) аналитически с помощью соответствующих формул:

f(x,y)=x&y

Последнее изменение: Суббота, 7 марта 2015, 09:21

Источник

Автор

Сообщение

Заголовок сообщения: Подсчитать число особых логических функций

Добавлено: 10 май 2021, 23:52

Начинающий

Зарегистрирован:
27 окт 2020, 13:56
Сообщений: 16
Cпасибо сказано: 4
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Здравствуйте, уважаемые участники форума. Не могу понять, как подойти к задаче по вычислению количества логических функций, подходящих под условие: [math](S cup L) — T _{0}[/math].
Буквы — множества по классификации Поста. К ним можно применять все формулы из алгебры множеств, но, как я понял, в данном случае их недостаточно. Я знаю следующие формулы: [math]left| T _{0} right| = left| T _{1} right| = 2 ^{2^{n} — 1}[/math], [math]left| T_{0} cap T_{1} right| = 2 ^{2^{n}-2}[/math], [math]left| S right| = 2 ^{2^{n-1}}[/math], [math]left| L right| = 2 ^{n+1}[/math], [math]LT_{0}T_{1} = LST_{0} = LST_{1} = LST_{0}T_{1}[/math] и некоторые другие свойства. Просят найти формулу числа таких вот функций.

Вернуться к началу

3D Homer	Заголовок сообщения: Re: Подсчитать число особых логических функций Добавлено: 11 май 2021, 00:56
	KuznetsovSA писал(а): Не могу понять, как подойти к задаче по вычислению количества логических функций, подходящих под условие: [math](S cup L) — T _{0}[/math]. Строго говоря, это не условие, а множество, и оно бесконечно. Если вас интересуют функции от [math]n[/math] переменных, то, думаю, их число можно найти по формуле [math]\|Soverline{T}_0\|+\|Loverline{T}_0\|-\|SLoverline{T}_0\|[/math].
Вернуться к началу

KuznetsovSA	Заголовок сообщения: Re: Подсчитать число особых логических функций Добавлено: 11 май 2021, 13:58
	3D Homer писал(а): Если вас интересуют функции от n n переменных, то, думаю, их число можно найти по формуле \|ST¯¯¯¯0\|+\|LT¯¯¯¯0\|−\|SLT¯¯¯¯0\| \|ST¯0\|+\|LT¯0\|−\|SLT¯0\| . Разве можно складывть мощности множеств не убедившись, что они не содержат общих элементов? Если вы точно знаете что эта формула работает, то не могли бы пояснить почему? Уже долго пытаюсь решить, поэтому написал програму на C которая счиает число таких функций для конкретного [math]n[/math]. Работает тупым перебором и проеркой. Вот что она насчитала: [math]1, 2, 4, 12, 136[/math] для функций от нуля, одной, двух переменных соответственно.
Вернуться к началу

KuznetsovSA	Заголовок сообщения: Re: Подсчитать число особых логических функций Добавлено: 11 май 2021, 15:23
	3D Homer писал(а): Где я предлагаю это делать: просто складывать? Вы написали 3D Homer писал(а): \|ST¯¯¯¯0\|+\|LT¯¯¯¯0\|−\|SLT¯¯¯¯0\| . А прямые скобки [math]left\| right\|[/math] обозначают взятие мощности множества, т.е. его длины. Возможно вы имели в виду что-то другое использовав эти скобки?
Вернуться к началу

Источник