Выражение уравнения функции по таблице значений

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

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

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

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

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

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

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 столбцов заполнены наборами аргументов, а оставшиеся столбцы заполняются значениями подфункций, входящих в запись функции, что позволяет упростить расчёт конечного значения функции за счёт уже промежуточных вычислений.

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

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

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

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

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

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

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

Чтобы задать функцию через вектор значений необходимо записать вектор из 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. Построим таблицу истинности для функции

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

Найдём наборы, на которых функция принимает истинное значение: < 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 строк:

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

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

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

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

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

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

Урок информатики по теме: «Excel: Построение графиков функций по заданным параметрам»

Цели урока:

• научить строить графики элементарных математических функций с помощью табличного процессора Excel;
• показать возможности использования программы Excel для решения задач по математике;
• закрепить навыки работы с Мастером диаграмм.

Задачи урока:

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

Тип урока:

• комбинированный

Учебники:

Информатика. Базовый курс 2-е издание/Под ред. С.В. Симоновича. — СПб.: Питер, 2004.-640с.:ил.

Технические и программные средства:

• Персональные компьютеры;
• Приложение Windows – электронные таблицы Excel.
• Проектор

Раздаточный материал:

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

План урока.

1. Организационный момент – 3 мин.
2. Проверка домашнего задания –10 мин.
3. Объяснение нового материала –20 мин.
4. Применение полученных знаний –20 мин.
5. Самостоятельная работа. – 20 мин
6. Подведение итогов урока. Домашнее задание – 7 мин.

Ход урока

Организационный момент

Проверка готовности учащихся к уроку, отметка отсутствующих, объявление темы и цели урока

Проверка домашнего задания. (фронтальный опрос)

Вопросы для проверки

1. Что представляет собой рабочая область программы Excel?
2. Как определяется адрес ячейки?
3. Как изменить ширину столбца, высоту строки?
4. Как ввести формулу в Excel?
5. Что такое маркер заполнения и для чего он нужен?
6. Что такое относительная адресация ячеек?
7. Что такое абсолютная адресация ячеек? Как она задается?
8. Что такое колонтитулы? Как они задаются?
9. Как задать поля печатного документа? Как изменить ориентацию бумаги?
10. Что такое функциональная зависимость у = f(х)? Какая переменная является зависимой, а какая независимой?
11. Как ввести функцию в Excel?
12. Что такое график функции у = f(х)?
13. Как построить диаграмму в Excel?

Объяснение нового материала.

При объяснении нового материала может быть использован файл Excel с шаблонами задач (Приложение 1), который выводится на экран с помощью проектора

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

Рассмотрим построение графиков функций на примере функции у = sin x.

Вид данного графика хорошо известен вам по урокам математики, попробуем построить его средствами Excel.

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

Чтобы создать таблицу, нужно определить

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

Задача 1.Построить график функции у = sin x на отрезке [– 2; 2] с шагом h = 0,5.

1. Заполним таблицу значений функции. В ячейку С4 введем первое значение отрезка: – 2
2. В ячейку D4 введем формулу, которая будет добавлять к лево-стоящей ячейки шаг: = В4 + $A$4
3. Маркером заполнения ячейки D4 заполним влево ячейки строки 4, до тех пор, пока получим значение другого конца отрезка: 2.
4. Выделим ячейку С5, вызовем Мастер функций, в категории математические выберем функцию SIN, в качестве аргумента функции выберем ячейку С4.
5. Маркером заполнения распространим эту формулу в ячейках строки 5 до конца таблицы.

Таким образом, мы получили таблицу аргументов (х) и значений (у) функции у = sin x на отрезке [-2;2] с шагом h = 0,5 :

6. Следующий шаг. Выделим таблицу и вызовем Мастер диаграмм. На первом шаге выберем во вкладке Нестандартные Гладкие графики.
7. На втором шаге во вкладке Ряд выполним:

В поле Ряд необходимо выделить ряд х и нажать на кнопку “Удалить” (график изменений х нам не нужен. График функции – это график изменения значений у)

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

8. На третьем шаге заполним вкладку Заголовки.

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

Для форматирования графика:

• Вызовем контекстное меню оси ОУ. Затем, выберем пункт Формат оси…. Во вкладке Шкала установим: цена основного деления: 1. Во вкладке Шрифт установим размер шрифта 8пт.
• Вызовем контекстное меню оси ОХ. Выберем пункт Формат оси….

Во вкладке Шкала установим: пересечение с осью ОУ установите номер категории 5 (чтобы ось ОУ пересекала ось ОХ в категории с подписью 0, а это пятая по счету категория).

Во вкладке шрифт установите размер шрифта 8пт. Нажмите на кнопку ОК.

Остальные изменения выполняются аналогично.

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

Применение полученных знаний.

Пригласить к проектору студента и сформулировать следующую задачу.

Задача 2. Построить график функции у = х 3 на отрезке [– 3; 3] с шагом h = 0,5.

1. Создать следующую таблицу: Создать таблица значений функции у = f(х).

2. В ячейку С4 ввести первое значение отрезка: –3
3. В ячейку D4 ввести формулу, которая будет добавлять к лево-стоящей ячейки шаг: = В4 + $A$4
4. Маркером заполнения ячейки D3 заполнить влево ячейки строки 3, до тех пор, пока не будет получено значение другого конца отрезка: 3.
5. В ячейку С5 ввести формулу вычисления значения функции: = С4^3
6. Маркером заполнения скопировать формулу в ячейки строки 5 до конца таблицы.

Таким образом, должна получиться таблица аргументов (х) и значений (у) функции у = х 3 на отрезке [–3;3] с шагом h = 0,5:

7. Выделить таблицу и вызвать мастер диаграмм. На первом шаге выбрать во второй вкладке Гладкие графики.
8. На втором шаге во вкладке Ряд выполнить:

• В поле Ряд выделить ряд х и нажать на кнопку “Удалить” (график изменений х нам не нужен. График функции – это график изменения значений у)
• В поле Подписи оси Х нажать на кнопку . Выделить в таблице ячейки со значениями х и нажать на кнопку . Подписи по горизонтальной оси станут такими, как у нас в таблице.

9. На третьем шаге заполнить вкладку Заголовки.

10. Пример полученного графика:
11. Оформить график.
12. Установить параметры страницы и размеры диаграмм таким образом, что бы все поместилось на одном листе альбомной ориентации.
13. Создать колонтитулы для данного листа (Вид Колонтитулы…):
14. Верхний колонтитул слева: график функции у = x 3

Сохранить документ своей папке под именем График.

Самостоятельная работа.

Работа по карточкам с индивидуальными заданиями. (Приложение 2)

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

1. Построить график функции y=f(x) на отрезке [a;b] с шагом h=c
2. Установить параметры страницы и размеры графика таким образом, что бы все поместилось на одном листе альбомной ориентации.
3. Создать колонтитулы для данного листа (Вид Колонтитулы…):

• Верхний колонтитул слева: график функции y=f(x)
• Нижний колонтитул в центре: ваши Ф.И.О. и дата

4. Сохранить в своей папке под именем “Зачетный график”
5. Вывести документ на печать.

После выполнения задания правильность каждого варианта проверяется с помощью проектора.

Графический и табличный способы

Этот видеоурок доступен по абонементу

У вас уже есть абонемент? Войти

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

Если у вас возникнет сложность в понимании темы, рекомендуем посмотреть урок «Функции»