Как найти вид функции по таблице

Главная

» 2015 » Октябрь » 27 » Как написать функцию по таблице значений функции

---

21:56 Как написать функцию по таблице значений функции

Как написать функцию по таблице значений функции Таблица значений функции – это значения функции (как правило, «у») при соответствующих значениях аргумента (как правило, «х»). Значения аргумента и функции определяют координаты точек, лежащих на графике функции. Эта статья расскажет вам, как написать линейную функцию по данной таблице ее значений. Шаги 1 Рассмотрите данную вам таблицу значений функции. Столбец «Х» соответствует значениям аргумента (координатам по оси «Х»), а столбец «Y» соответствует значениям функции (координатам по оси «Y») Стандартная форма линейной функции: у = kx + b, где k – угловой коэффициент, b – смещение графика функции по оси «Y». 2 Для вычисления k и b подставьте данные вам значения «х» и «у» в стандартную форму линейной функции. В нашем примере: х = -6, у = -3. Поэтому: -3 = k(-6) + b В нашем примере: х = 0 и у = -1. Поэтому: -1 = k(0) + b. Следовательно b = -1. Вы нашли, что b = -1. 3 Теперь вычислите k. Будьте внимательны при перемножении отрицательного числа, стоящего за скобками, и членов, находящихся внутри скобок. При перемножении двух отрицательных чисел вы получите положительное число, а при перемножении положительного и отрицательного чисел вы получите отрицательное число. 4 Подставьте найденное значение b в уравнение -3 = k(-6) + b (см. выше). Вы получите -3 = -6k — 1. Обособьте k на одной стороне уравнения, перенеся 1 на другую сторону уравнения. Вы получите: -6k = -2. Разделите обе части уравнения на -6, чтобы избавиться от коэффициента при k. Вы получите: (-6k)/(-6) = (-2)/(-6) Таким образом, k = 1/3 и b = -1. Наконец, запишите функцию: у = (1/3)x-1 5 Также вы можете использовать формулу k = (y2-y1)/(x2-x1). В нашем примере подставьте в эту формулу значения х1 = -6; у1 = -3 и x2 = 0; y2 = -1. k = {-1 — (- 3)}/{0 — (- 6)} k = 2/6 = 1/3 Теперь вычислите b, используя стандартную форму уравнения (при х = -6 и у = -3). -3 = 1/3 (-6) + b b = -1 Уравнение функции: у = (1/3)x — 1

1 2 3 4 5 Категория: Вопросы и ответы | Просмотров: 567 | | Рейтинг: 0.0/0

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

Рис.1 Табличные значения функции

Для реализации данного метода необходимо предварительно определить значение функции в ряде точек на заданном интервале изменения аргумента (построить функцию по точкам). Данные сводятся в таблицу и сохраняются в неизменном виде во FLASH-памяти программ или в энергонезависимой памяти иного типа. Теперь отыскание значений функции Y = F(X) будет сводиться к простому выбору из таблицы, заранее посчитанных, Y_i для соответствующих X_i. Сам интервал разбивается на n участков. Расстояние между двумя соседними точками d = X_i+1 — X_i будет шагом таблицы. Число n всегда надо выбирать кратным целой степени двойки, а d, если это возможно, одинаковым в пределах всей таблицы (таблица с фиксированным шагом). На рис.1 показана функция Y = F(X), а т.A(X_i,Y_i) и т.B(X_i+1,Y_i+1) это два её соседних табличных значения. Для того чтобы определить функцию в произвольной точке, например в т.С(X,Y), прибегают к линейной интерполяции, замещая участок функции прямой. В нашем случае это прямая AB. Искомая т.С отобразится на ней как т.С’. В расчеты будет внесена некоторая абсолютная погрешность Δ = |F(C) — F(C’)|, которая не превзойдет максимально возможного значения Δmax = |F(B) — F(A)| если функция не поменяет свой знака на этом участке.

Уравнение прямой проведенной через две точки имеет вид:
(X – X_i)/(X_i+1 – X_i) = (Y – Y_i)/(Y_i+1 – Y_i).  (1)

Если учесть, что в (1) d = X_i+1 — X_i, то для текущих координат получим окончательную формулу:   
Y = Y_i + (X – X_i)* (Y_i+1 – Y_i)/d.  (2)

Таким образом, будем иметь следующий порядок расчета. Сначала, делением заданного X на шаг таблицы d, определяем в каком месте таблицы находится искомое значение функции Y = F(X). Частное от этого деления даст индекс i аргумента X_i в таблице, по которому и определяется Y_i. Если остаток от деления нулевой, то Y совпадает с Y_i и расчет заканчивается. В противном случае из таблицы нужно взять следующее значение Y_i+1, а искомое Y определить в соответствии с (2). Ниже приведена подпрограмма, основанная на этом алгоритме. Она предназначена для совместного использования с таблицами функций sinX и arcsinX (приведены ниже). Скорость вычисления в самом худшем случае составляет всего 46(!) машинных циклов.

;     Подпрограмма вычисления функций c использованием
;               табличной конвертации 
; R17:R16 – входное значение аргумента в формате (8.8), 
;  лежащее в диапазоне 0…128.0
; на n = 128 участков 2-байтовых значений функции  
; R21:R20 – значение функции на выходе из подпрограммы
; R0,R1,R18,R19,R30,R31 – вспомогательные регистры
 			   
tbl_func:  
    dec   R17      ;уменьшаем на 1 аргумент поскольку нулевое
    clr   R18      ;значение функции в таблице не хранится
	ldi   ZL,low(2*tabl)  ;заносим в указатель ZH:ZL адрес
	ldi   ZH,high(2*tabl) ;начала таблицы
    lsl   R17      ;удваиваем значение аргумента, чтобы учесть
	rol   R18      ;2-байтовый формат данных в таблице
	add   ZL,R17   ;добавляем к указателю смещение
	adc   ZH,R18
	lpm   R17,Z+   ;извлекаем из таблицы значение R18:R17 = Yi
    lpm   R18,Z+  	
    tst   R16      ;если остаток R16=0, то в R17:R16 уже
	brne  PC+2      ;находится нужное значение
    ret            ;и поэтому выходим из подпрограммы
    lpm   R19,Z+   ;в ином случае извлекаем из таблицы
    lpm   R20,Z    ;очередное значение R20:R19 = Yi+1
	sub   R19,R17  ;находим разность R20:R19 = Yi+1 - Yi
	sbc   R20,R18
	mul   R20,R16  ;находим смещение относительно точки Yi
	movw  R20,R0   ;R21:R20:R19 = (Yi+1 - Yi)*(X - Xi)/d в
	mul   R19,R16  
	mov   R19,R0   
	clr   R16      
	add   R20,R1
	adc   R21,R16
    sec            ;если R19 ≥ 1/2, то устанавливаем флаг
    sbrs  R19,7    ;переноса для коррекции результата
    clc
    adc   R17,R20  ;находим окончательно значение функции
	adc   R18,R21  ;R21:R20 = Y = Yi + (X – Xi)*(Yi+1 – Yi)/d
    ret

;         Таблица значений функции sinX 
; диапазон изменения аргумента 0…900, шаг d = (90/128)0
; значения функции хранятся в виде 32768*sinX

sin_tabl: 
 .dw 0x0192,0x0324,0x04B6,0x0648,0x07D9,0x096B,0x0AFB,0x0C8C
 .dw 0x0E1C,0x0FAB,0x113A,0x12C8,0x1455,0x15E2,0x176E,0x18F9 
 .dw 0x1A83,0x1C0C,0x1D93,0x1F1A,0x209F,0x2224,0x23A7,0x2528 
 .dw 0x26A8,0x2827,0x29A4,0x2B1F,0x2C99,0x2E11,0x2F87,0x30FC 
 .dw 0x326E,0x33DF,0x354E,0x36BA,0x3825,0x398D,0x3AF3,0x3C57 
 .dw 0x3DB8,0x3F17,0x4074,0x41CE,0x4326,0x447B,0x45CD,0x471D 
 .dw 0x486A,0x49B4,0x4AFB,0x4C40,0x4D81,0x4EC0,0x4FFB,0x5134 
 .dw 0x5269,0x539B,0x54CA,0x55F6,0x571E,0x5843,0x5964,0x5A82 
 .dw 0x5B9D,0x5CB4,0x5DC8,0x5ED7,0x5FE4,0x60EC,0x61F1,0x62F2 
 .dw 0x63EF,0x64E9,0x65DE,0x66D0,0x67BD,0x68A7,0x698C,0x6A6E 
 .dw 0x6B4B,0x6C24,0x6CF9,0x6DCA,0x6E97,0x6F5F,0x7023,0x70E3 
 .dw 0x719E,0x7255,0x7308,0x73B6,0x7460,0x7505,0x75A6,0x7642 
 .dw 0x76D9,0x776C,0x77FB,0x7885,0x790A,0x798A,0x7A06,0x7A7D 
 .dw 0x7AEF,0x7B5D,0x7BC6,0x7C2A,0x7C89,0x7CE4,0x7D3A,0x7D8A 
 .dw 0x7DD6,0x7E1E,0x7E60,0x7E9D,0x7ED6,0x7F0A,0x7F38,0x7F62 
 .dw 0x7F87,0x7FA7,0x7FC2,0x7FD9,0x7FEA,0x7FF6,0x7FFE,0x8000     

;        Таблица значений функции arcsinX 
; диапазон изменения аргумента 0…1, шаг d = 1/128
; значения функции хранятся в виде 32768*arcsinX рад

arcsin_tabl:
 .dw 0x0100,0x0200,0x0300,0x0400,0x0500,0x0601,0x0701,0x0801
 .dw 0x0902,0x0A03,0x0B03,0x0C05,0x0D06,0x0E07,0x0F09,0x100B
 .dw 0x110D,0x120F,0x1312,0x1415,0x1518,0x161C,0x1720,0x1825
 .dw 0x1929,0x1A2F,0x1B34,0x1C3A,0x1D41,0x1E48,0x1F50,0x2058
 .dw 0x2161,0x226A,0x2374,0x247E,0x2589,0x2695,0x27A1,0x28AE
 .dw 0x29BC,0x2ACB,0x2BDA,0x2CEB,0x2DFC,0x2F0D,0x3020,0x3134
 .dw 0x3249,0x335E,0x3475,0x358C,0x36A5,0x37BF,0x38DA,0x39F6
 .dw 0x3B13,0x3C32,0x3D52,0x3E73,0x3F95,0x40B9,0x41DE,0x4305
 .dw 0x442E,0x4558,0x4683,0x47B1,0x48E0,0x4A10,0x4B43,0x4C78
 .dw 0x4DAE,0x4EE7,0x5022,0x515F,0x529E,0x53E0,0x5524,0x566B
 .dw 0x57B4,0x5900,0x5A4F,0x5BA1,0x5CF5,0x5E4D,0x5FA9,0x6107
 .dw 0x626A,0x63D0,0x653A,0x66A8,0x681A,0x6991,0x6B0D,0x6C8D
 .dw 0x6E13,0x6F9E,0x712F,0x72C6,0x7463,0x7608,0x77B3,0x7966
 .dw 0x7B21,0x7CE6,0x7EB3,0x808B,0x826D,0x845C,0x8657,0x8860
 .dw 0x8A79,0x8CA3,0x8EE0,0x9132,0x939C,0x9621,0x98C7,0x9B91
 .dw 0x9E89,0xA1B7,0xA52B,0xA8FA,0xAD4B,0xB268,0xB90D,0xC910

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

Теги:

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

Рис. 1 (см. Приложение 2)

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

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

При анализе исходной функции необходимо решить
следующие задачи:

1. определение максимума (минимума) данной функции
   на заданном интервале,
2. определение возрастания и/или убывания функции
   на заданном интервале,
3. определение четности заданной функции,
4. определение периодичности заданной функции,
5. определение значения первой производной данной
   функции и наличия экстремумов.

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

Приложение 1

Задача 1.
Для заданной функции на заданном интервале
аргумента определить ее минимальное и
максимальное значения.

Решение.
Для решения этой задачи построим таблицу
ВыводаРезультатов в виде

	D	E
1	комментарии	Значения
2	Макс f(X)	<формула>
3	Мин f(X)	<формула>

В мастере функций Excel имеются функции МАКС(…) и
МИН(…), позволяющие решить нашу задачу. Для этого
необходимо в ячейки Е2 и Е3 ввести соответственно
формулы:

E2 => [=МАКС(с10:с50)]
и
E3 => [=МИН(с10:с50)]

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

ЗАДАЧА РЕШЕНА.

Задача 2.
Определение возрастания и/или убывания функции
на заданном интервале.

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

D11 => [=ЕСЛИ(a11<>””;ЗНАК(D11-D10);””)]
и “протянем” ее до строки №50.

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

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

	F	G
1	КОММЕНТАРИИ	ЗНАЧЕНИЯ
2	Признак возрастания	<формула>
3	Признак убывания	<формула>

Для этого в ячейки g2 и g3 соответственно вводим
формулы:

G2 => [=СуммЕсли(d11:d50;”>0”)]
G3 => [=СуммЕсли(d11:d50;”<0”)]

Таблицу ВыводаРезультатов дополним строкой

	D	E
1	комментарии	значения
2	Макс f(X)	=МАКС(с10:с50)
3	Мин f(X)	=МИН(с10:с50)
4	Возрастание/Убывание	<формула>

И для определения характера изменения заданной
функции остается ввести в ячейку Е4 формулу:

E4 => [=ЕСЛИ(g2>0; ЕСЛИ(g3<0;”и то и
другое”;”возрастает”);”убывает”)

ЗАДАЧА РЕШЕНА.

Задача 3.
Определение четности данной.

Решение.
Для решения данной задачи необходимо знание
аналитического представления исходной функции,
так как признаком четности функции является
равенство f(X) = f(-X).

Для решения данной задачи в расчетной таблице
построим дополнительный столбец. В ячейку Е10
введем формулу

E10 => [=f(b10) – f(-b10)]
и “протянуть” ее до строки №50.

Таблицу ВыводаРезультатов дополним строкой

	D	E
1	комментарии	значения
2	Макс f(X)	=МАКС(с10:с50)
3	Мин f(X)	=МИН(с10:с50)
4	Возрастание/Убывание	[=ЕСЛИ(g2>0; ЕСЛИ(g3<0;”и то и другое”;”возрастает”);”убывает”)
5	четность	<формула>

В ячейку Е4 таблицы ВыводаРезультатов вводим
формулу.

E4 => [ЕСЛИ(ABS(СУММ(E10:E50))<0,000001; “ЧЕТНАЯ”;
“НЕЧЕТНАЯ”)

ЗАДАЧА РЕШЕНА.

Задача 4.
Определить является ли введенный период
периодом заданной функции.

Решение.
Для решения данной задачи необходимо знание
аналитического представления исходной функции,
так как признаком периодичности функции
является равенство f(Х) = f(X+<период>).

Для данной задачи добавим в таблице
ВводаИсходнойИнформации строку №6, в которой
введем численное значение предполагаемого
периода.

	А	В
1	КОММЕНТАРИИ	ЗНАЧЕНИЯ
2	Xn	<значение>
3	Xk	<значение>
4	Shag	<значение>
5	N	<формула>
6	период	<значение>

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

Далее для решения данной задачи построим
дополнительный столбец в расчетной таблице, для
этого в ячейку F11 введем формулу

F10 => [=ЕСЛИ(a10<>””;f(b10)-f(b10+$b$6);””)]

и “потягиваем” эту формулу до строки №50.

В таблице ВыводаРезультатов добавим строчку.

	D	E
1	комментарии	значения
2	Макс f(X)	=МАКС(с10:с50)
3	Мин f(X)	=МИН(с10:с50)
4	четность	=ЕСЛИ(g2>0; ЕСЛИ(g3<0;”и то и другое”;”возрастает”);”убывает”)
5	период	<формула>

В ячейке Е5 необходимо ввести формулу

Е5 => [=ЕСЛИ(СУММ(f10:f50)<0,01;”период”;”не
период”)]

Если данное значение предполагаемого периода
не подходит, то его можно изменить.

ЗАДАЧА РЕШЕНА.

Задача 5.
Для заданной функции определить:

• значения первой производной данной функции,
• наличия и количество экстремумов.

Решение.
Для решения первой части задачи, то есть
определения первой производной воспользуемся ее
разностным определение.

Построим столбец. Для этого в ячейку G11 вводим
формулу:

G11 => [= ЕСЛИ(a11<>””; ABS((c11-c10)/(b11-b10));””)]

и “протягиваем ее до строки с №50.

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

Для решения второй части задачи, то есть
определения наличия и количества экстремумов на
заданной функции в таблицу ВыводаРезультатов
дополнить строкой.

	D	E
1	комментарии	значения
2	Макс f(X)	=МАКС(с10:с50)
3	Мин f(X)	=МИН(с10:с50)
4	четность	=ЕСЛИ(g2>0; ЕСЛИ(g3<0;”и то и другое”;”возрастает”);”убывает”)
5	период	[=ЕСЛИ(СУММ(f10:f50)<0,01;”период”; ”не период”)]
6	Количество Экстремумов.	<формула>

В ячейке Е6 необходимо ввести формулу

E6 => [=СчетЕсли(g11:g50;”<0,05”)]

ЗАДАЧА РЕШЕНА.

Рис 2, см. Приложение 3

На рис.2 приведена построенная таблица
решения задач.

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

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

Мультиплексором можно описать любую таблицу истинности на n входов, если n — количество адресных входов мультиплексора (могу рассказать подробнее каким образом, если интересно).

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

Из таблицы истинности можно восстановить её функцию разными методами, один из распространённых и наглядных методов — картами Карно. На первый взгляд выглядит как чёрная магия, но надо чуточку напрячь мозг — и всё встаёт на свои места. Если надо, могу объяснить, как им пользоваться.

Таблица истинности

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

Клавиша	Оператор
!	¬	Отрицание (НЕ)
|	|	Штрих Шеффера (И-НЕ)
#	↓	Стрелка Пирса (ИЛИ-НЕ)
*	&	Конъюнкция (И)
+	v	Дизъюнкция (ИЛИ)
^	⊕	Исключающее ИЛИ, сумма по модулю 2 (XOR)
@	→	Импликация (ЕСЛИ-ТО)
%	←	Обратная импликация
=	≡ (

, ↔)
Эквивалентность (РАВНО)

bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Для ввода данных в виде логической схемы используйте этот сервис.
Для булевой функции, заданной вектором значений (например, 00111011 ) используйте ввод данных через таблицу.

Правила ввода логической функции

1. Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
2. Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
3. Максимальное количество переменных равно 10 .

Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможных логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.

Уравнение функции по таблице истинности

2) Логическое сложение или дизъюнкция:

Дизъюнкция — это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выраженbя ложны.
Обозначение: F = A v B.

Таблица истинности для дизъюнкции

A	B	F
1	1	1
1	0	1
0	1	1
0	0	0

3) Логическое отрицание или инверсия:

Инверсия — это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.

Обозначение: F = ¬ A.

Таблица истинности для инверсии

4) Логическое следование или импликация:

Импликация — это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.

«A → B» истинно, если из А может следовать B.

Обозначение: F = A → B.

Таблица истинности для импликации

A	B	F
1	1	1
1	0	0
0	1	1
0	0	1

5) Логическая равнозначность или эквивалентность:

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

Построение таблицы истинности. СДНФ. СКНФ. Полином Жегалкина.

Онлайн калькулятор позволяет быстро строить таблицу истинности для произвольной булевой функции или её вектора, рассчитывать совершенную дизъюнктивную и совершенную конъюнктивную нормальные формы, находить представление функции в виде полинома Жегалкина, строить карту Карно и классифицировать функцию по классам Поста.

Калькулятор таблицы истинности, СКНФ, СДНФ, полинома Жегалкина

введите функцию или её вектор

Построено таблиц, форм:

Как пользоваться калькулятором

1. Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)
2. Укажите действия, которые необходимо выполнить с помощью переключателей
3. Укажите, требуется ли вывод решения переключателем «С решением»
4. Нажмите на кнопку «Построить»

Видеоинструкция к калькулятору

Используемые символы

В качестве переменных используются буквы латинского и русского алфавитов (большие и маленькие), а также цифры, написанные после буквы (индекс переменной). Таким образом, именами переменных будут: a , x , a1 , B , X , X1 , Y1 , A123 и так далее.

Для записи логических операций можно использовать как обычные символы клавиатуры ( * , + , ! , ^ , -> , = ), так и символы, устоявшиеся в литературе ( ∧ , ∨ , ¬ , ⊕ , → , ≡ ). Если на вашей клавиатуре отсутствует нужный символ операции, то используйте клавиатуру калькулятора (если она не видна, нажмите «Показать клавиатуру»), в которой доступны как все логические операции, так и набор наиболее часто используемых переменных.

Для смены порядка выполнения операций используются круглые скобки ().

Обозначения логических операций

• И (AND): & • ∧ *
• ИЛИ (OR): ∨ +
• НЕ (NOT): ¬ !
• Исключающее ИЛИ (XOR): ⊕ ^
• Импликация: -> → =>
• Эквивалентность: =

Что умеет калькулятор

• Строить таблицу истинности по функции
• Строить таблицу истинности по двоичному вектору
• Строить совершенную конъюнктивную нормальную форму (СКНФ)
• Строить совершенную дизъюнктивную нормальную форму (СДНФ)
• Строить полином Жегалкина (методами Паскаля, треугольника, неопределённых коэффициентов)
• Определять принадлежность функции к каждому из пяти классов Поста
• Строить карту Карно
• Минимизировать ДНФ и КНФ
• Искать фиктивные переменные

Что такое булева функция

Булева функция f(x₁, x₂, . x_n) — это любая функция от n переменных x₁, x₂, . x_n, в которой её аргументы принимают одно из двух значений: либо 0, либо 1, и сама функция принимает значения 0 или 1. То есть это правило, по которому произвольному набору нулей и единиц ставится в соответствие значение 0 или 1. Подробнее про булевы функции можно посмотреть на Википедии.

Что такое таблица истинности?

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

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

Логические операции

Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения более простых. В качестве основных операций обычно называют конъюнкцию (∧ или &), дизъюнкцию (∨ или |), импликацию (→), отрицание (¬), эквивалентность (=), исключающее ИЛИ (⊕).

Таблица истинности логических операций

a	b	a ∧ b	a ∨ b	¬a	¬b	a → b	a = b	a ⊕ b
0	0	0	0	1	1	1	1	0
0	1	0	1	1	0	1	0	1
1	0	0	1	0	1	0	0	1
1	1	1	1	0	0	1	1	0

Как задать логическую функцию

Есть множество способов задать булеву функцию:

• таблица истинности
• характеристические множества
• вектор значений
• матрица Грея
• формулы

Рассмотрим некоторые из них:

Чтобы задать функцию через вектор значений необходимо записать вектор из 2 n нулей и единиц, где n — число аргументов, от которых зависит функция. Например, функцию двух аргументов можно задать так: 0001 (операция И), 0111 (операция ИЛИ).

Чтобы задать функцию в виде формулы, необходимо записать математическое выражение, состоящее из аргументов функции и логических операций. Например, можно задать такую функцию: a∧b ∨ b∧c ∨ a∧c

Способы представления булевой функции

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

• Совершенная дизъюнктивная нормальная форма (СДНФ)
• Совершенная конъюнктивная нормальная форма (СКНФ)
• Алгебраическая нормальная форма (АНФ, полином Жегалкина)

Совершенная дизъюнктивная нормальная форма (ДНФ)

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

Например, ДНФ является функция ¬a bc ∨ ¬a ¬b c ∨ ac, но не является СДНФ, так как в последней конъюнкции отсутствует переменная b.

Совершенная конъюнктивная нормальная форма (КНФ)

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

Например, КНФ является функция (a ∨ b) ∧ (a ∨ b ∨ c), но не является СДНФ, так как в первой дизъюнкции отсутствует переменная с.

Алгебраическая нормальная форма (АНФ, полином Жегалкина)

Алгебраическая нормальная форма, полином Жегалкина — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции, а в качестве сложения — исключающее ИЛИ.

Примеры полиномов Жегалкина: 1, a, a⊕b, ab⊕a⊕b⊕1

Алгоритм построения СДНФ для булевой функции

1. Построить таблицу истинности для функции
2. Найти все наборы аргументов, на которых функция принимает значение 1
3. Выписать простые конъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 0, то она входит в конъюнкцию с отрицанием, а иначе без отрицания
4. Объединить все простые конъюнкции с помощью дизъюнкции

Алгоритм построения СКНФ для булевой функции

1. Построить таблицу истинности для функции
2. Найти все наборы аргументов, на которых функция принимает значение 0
3. Выписать простые дизъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 1, то она входит в дизъюнкцию с отрицанием, а иначе без отрицания
4. Объединить все простые дизъюнкции с помощью конъюнкции

Алгоритм построения полинома Жегалкина булевой функции

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

1. Построить таблицу истинности для функции
2. Добавить новый столбец к таблице истинности и записать в 1, 3, 5. ячейки значения из тех же строк предыдущего столбца таблицы истинности, а к значениям в строках 2, 4, 6. прибавить по модулю два значения из соответственно 1, 3, 5. строк.
3. Добавить новый столбец к таблице истинности и переписать в новый столбец значения 1, 2, 5, 6, 9, 10. строк, а к 3, 4, 7, 8, 11, 12. строкам аналогично предыдущему пункту прибавить переписанные значения.
4. Повторить действия каждый раз увеличивая в два раза количество переносимых и складываемых элементов до тех пор, пока длина не станет равна числу строк таблицы.
5. Выписать булевы наборы, на которых значение последнего столбца равно единице
6. Записать вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора записать единицу) и объединить их с помощью операции исключающего ИЛИ.

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

Построим совершенные дизъюнктивную и дизъюнктивную нормальные формы, а также полином Жегалкина для функции трёх переменных F = ¬a b∨ ¬b c∨ca

1. Построим таблицу истинности для функции

a	b	c	¬a	¬a ∧b	¬b	¬b ∧c	¬a ∧b∨ ¬b ∧c	c∧a	¬a ∧b∨ ¬b ∧c∨c∧a
0	0	0	1	0	1	0	0	0	0
0	0	1	1	0	1	1	1	0	1
0	1	0	1	1	0	0	1	0	1
0	1	1	1	1	0	0	1	0	1
1	0	0	0	0	1	0	0	0	0
1	0	1	0	0	1	1	1	1	1
1	1	0	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	1	1

Построение совершенной дизъюнктивной нормальной формы:

Найдём наборы, на которых функция принимает истинное значение: < 0, 0, 1 > < 0, 1, 0 > < 0, 1, 1 > < 1, 0, 1 >

В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием:

Объединим конъюнкции с помощью дизъюнкции и получим совершенную дизъюнктивную нормальную форму:

Построение совершенной конъюнктивной нормальной формы:

Найдём наборы, на которых функция принимает ложное значение: < 0, 0, 0 > < 1, 0, 0 >

В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием:

Объединим дизъюнкции с помощью конъюнкции и получим совершенную конъюнктивную нормальную форму:

Построение полинома Жегалкина:

Добавим новый столбец к таблице истинности и запишем в 1, 3, 5 и 7 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 2, 4, 6 и 8 сложим по модулю два со значениями из соответственно 1, 3, 5 и 7 строк:

a	b	c	F	1
0	0	0	0	→	0
0	0	1	1	⊕ 0	1
0	1	0	1	→	1
0	1	1	1	⊕ 1	0
1	0	0	0	→	0
1	0	1	1	⊕ 0	1
1	1	0	0	→	0
1	1	1	1	⊕ 0	1

Добавим новый столбец к таблице истинности и запишем в 1 и 2, 5 и 6 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 3 и 4, 7 и 8 сложим по модулю два со значениями из соответственно 1 и 2, 5 и 6 строк:

a	b	c	F	1	2
0	0	0	0	0	→	0
0	0	1	1	1	→	1
0	1	0	1	1	⊕ 0	1
0	1	1	1	0	⊕ 1	1
1	0	0	0	0	→	0
1	0	1	1	1	→	1
1	1	0	0	0	⊕ 0	0
1	1	1	1	1	⊕ 1	0

Добавим новый столбец к таблице истинности и запишем в 1 2, 3 и 4 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 5, 6, 7 и 8 сложим по модулю два со значениями из соответственно 1, 2, 3 и 4 строк:

a	b	c	F	1	2	3
0	0	0	0	0	0	→	0
0	0	1	1	1	1	→	1
0	1	0	1	1	1	→	1
0	1	1	1	0	1	→	1
1	0	0	0	0	0	⊕ 0	0
1	0	1	1	1	1	⊕ 1	0
1	1	0	0	0	0	⊕ 1	1
1	1	1	1	1	0	⊕ 1	1

Окончательно получим такую таблицу:

a	b	c	F	1	2	3
0	0	0	0	0	0	0
0	0	1	1	1	1	1
0	1	0	1	1	1	1
0	1	1	1	0	1	1
1	0	0	0	0	0	0
1	0	1	1	1	1	0
1	1	0	0	0	0	1
1	1	1	1	1	0	1

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

Объединяя полученные конъюнкции с помощью операции исключающего или, получим полином Жегалкина: c⊕b⊕bc⊕ab⊕abc

Programforyou — это сообщество, в котором Вы можете подтянуть свои знания по программированию, узнать, как эффективно решать те или иные задачи, а также воспользоваться нашими онлайн сервисами.