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

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

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

Другие примеры решений о булевых функциях:

Видео:Дискретная математика. Видео 3. Полнота системы функций.Скачать

Задачи и решения о классах Поста и полноте

Задача 1. Является ли полной система булевых функций, состоящая из дизъюнкции и импликации?

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

$$ f_1=x_1 wedge x_2,, f_2=0, , f_3=x_1 sim x_2.$$

Задача 3. Определить, к каким классам Поста относится $F = neg x1 x3 vee x1 neg x3$, добавить (если это необходимо) к $F$ элементарные функции, чтобы полученное множество было полным.

Задача 4. Является ли полной система функций?

Задача 5. а) Используя эквивалентные преобразования получить тупиковую ДНФ;
б)Построить функционально полную систему функций так, чтобы эта система была базисом и содержала $f (x, y, z, p)$

$$f (x, y, z, p)= bar p downarrow y to z vee p Leftrightarrow y oplus z |x Leftarrow p$$

Задача 6. Проверить леммы о нелинейной, немонотонной и несамодвойственной функциях для функции

Задача 7. Даны функции $f$ (таблица 2) и $w$ (таблица 3).
а) Вычислить таблицу значений функции $f$.
б) Найти минимальные ДНФ функций $f$ и $w$.
в) Выяснить полноту системы $$. Если система не полна, дополнить систему функцией $g$ до полной системы.
г) Из функциональных элементов, реализующих функции полной системы $$ или $$, построить функциональные элементы, реализующие базовые функции $$

$$ f=((x_3 to (x_1sim x_2))oplus (overline to overline))to (overline|overline),\ w = (0, 1, 1, 0, 0, 1, 0, 1). $$

Видео:Полные системы булевых функций БазисыСкачать

Решение задач на заказ

Выполняем для студентов очников и заочников решение заданий, контрольных и практических работ по дискретной математике, в том числе задания о проверке полноты системы булевых функций на заказ. Также оказываем помощь в сдаче тестов. Подробное оформление, таблицы, графики, пояснение, использование специальных программ при необходимости. Стоимость примера от 150 рублей , оформление производится в Word, срок от 2 дней.

Видео:20-1 Полные системы булевых функцийСкачать

Классы Поста. Полнота системы функций

Математик Эмиль Пост ввел следующие замкнутые классы булевых функций:

• $T_0$ — Сохраняющие константу 0
• $T_1$ — Сохраняющие константу 1
• $S$ — Самодвойственные функции
• $M$ — Монотонные функции
• $L$ — Линейные функции

Теорема Поста (о полноте): Набор булевых функций $K$ является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов $S,M,L,T0,T1$.

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

Самые известные полные системы булевых функций:

• $wedge, vee, neg$ — (конъюнкция, дизъюнкция, отрицание). Используется для представления в виде ДНФ и КНФ.
• $wedge, oplus, 1$ — (конъюнкция, сложение по модулю два, константа один). Используется для представления в виде полинома Жегалкина.
• Штрих Шеффера
• Стрелка Пирса

Видео:Важнейшие замкнутые классы. Теорема ПостаСкачать

Функциональная полнота систем булевых функций

Видео:Матан за час. Шпаргалка для первокурсника. Высшая математикаСкачать

I. Функциональная полнота систем булевых функций

Замыкание и замкнутые классы Обосновать следующие свойства замыкания и привести примеры: [[M]]=[M]; Выписать все, зависящие только от переменных х1, х2, х3 и попарно неконгруентные функции из замыкания множества P. Функции f1 и f2 называются конгруэнтными, если одна из них может быть получена из другой заменой переменных, исключая отождествление переменных. Например, функции и — конгруэнтные, а функции xy и zz не являются конгруентными. P= Из системы D, полной для замкнутого класса M=[D], выделить базис: D=[xy, x∨y, x⊕y⊕z⊕u, x→y>. Доказать, что предполный класс замкнут. Сведением к заведомо полной в Р2 системе показать, что множество D полно в Р2. D=. Пусть М1 и M2 такие замкнутые классы в Р2, что М1М2≠∅. Привести примеры конкретных классов М1 и М2, которые удовлетворяли бы следующим условиям: М1∩М2=∅, М2М1≠∅, [M1∪M2]=M1∪M2. Определить к каким предполным классам принадлежат следующие функции: (x → y) ⊕ ((x ↓ y) | (-x ↔ yz ));

Видео:21-2 Теорема Поста о полнотеСкачать

1.2. Классы функций, сохраняющих 0 и 1, Т0 и Т1

Докажите, что для любых множеств D1, D2⊆P2 справедливо включение [D1]∪[D2]⊂[D1∪D2]. Приведите пример, когда [D1]∪[D2]⊂[D1∪D2].

Видео:Высшая математика. Линейные пространства. Векторы. БазисСкачать

1.3. Класс самодвойственных функций, S

Видео:СПОРИМ ты поймешь Математику — Функция и ее свойства, Область определения, Нули ФункцииСкачать

1.4. Класс монотонных функций, М

Видео:Свойства функции. Промежутки знакопостоянства. 10 класс.Скачать

1.5. Класс линейных функций, L

1.6. Критерий Поста

Используя критерий функциональной полноты Поста, выяснить, полна ли в Р2 система функций D: P=; Используя критерий полноты, выяснить, полна ли в Р2 система D D=(SM)∪(L(T0∪T1));

Видео:Всё о квадратичной функции. Парабола | Математика TutorOnlineСкачать

II Элементы теории алгоритмов

K1 = q11301

3.Построить композицию Т1Т2 машин Тьюринга Т1 и Т2 (по паре состояний (q10, q21)) и найти результат применения композиции T1T2 к слову P (q20 — заключительное состояние машины Т2), если программы машин Т1 и Т2 заданы таблицами:

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

Видео:§43 Линейные пространстваСкачать

III Исчисление высказываний

3.1. ⊢

Доказать, что следующие правила допустимы: Используя замкнутые семантические таблицы, доказать, что следующие выражения являются тавтологиями. Используя метод резолюций, доказать следования: ⊢(c∨d);

Видео:ЧТО НАДО ГОВОРИТЬ ЕСЛИ НЕ СДЕЛАЛ ДОМАШКУ!Скачать

IV. Логика предикатов. Основные определения.

Сигнатура языка логики предикатов (PrL) обозначается, где С – множество констант, F – множество функциональных символов, R — множество предикатных символов.

Алгебраической системой M = (D, Σ) сигнатуры Σ называется непустое множество D, где каждому n-местному предикатному (функциональному) символу сопоставлен n-местный предикат (функция) на D, а каждой предметной константе с∈С сопоставлен некоторый объект из D. Алгебраическая система M называется моделью, если сигнатура Σ не содержит функциональных символов.

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

13.Рассмотрим модели с одним двуместным предикатом R(x, y). Записать, что данный предикат

Рефлексивен; Являются ли тождественно истинными следующие формулы: (∃xP(x)→∀xP(x)); Привести к пренексной нормальной форме, считая U и B бескванторными формулами: ¬∃x∀y∃z∀uU; Для формулы ∀x∀y∃z∃t (P(x, t) & ¬P(y, z)) построить сколемовскую формулу. Для любой системы ((М, P), где М=, найти подходящее обогащение.

Видео:Как найти область определения функции? #shortsСкачать

V. Подстановки

Если free (x, t,A), то ├ (A → ∃x A(x)); Предположим, что драконы существуют, и мы поймали одного из них. Запишите следующие предложения в виде хорновских дизъюнктов: Всякий дракон, живущий в зоопарке, несчастен; Пусть (, P2) – модель сигнатуры языка логики предикатов и задана функция интерпретации I такая, что (a, a), (b, b) ∈ I(P), а (a, b), (b, a) ∉I(P). Определить, являются ли следующие формулы истинными в данной интерпретации: ∀x∃yP(x, y); Приведите к предваренной нормальной форме следующие предложения:

c.

Определить теоретико-множественную форму следующих предложений: A1:

16.Докажите с помощью замкнутых семантических таблиц общезначимость следующих предложений:

VI. Унификация. Метод резолюции

Определить, какие из следующих множеств предложений унифицируемы. Если они унифицируемы, найдите наиболее общий унификатор (НОУ). S=<

,

>; Предположим, что верны утверждения, представленные ниже: Существует хотя бы один дракон.

22.Можно ли из следующей совокупности фактов:

А1: Марк был римлянином.

А2: Цезарь был диктатором.

А3: Те римляне, которые ненавидели диктатора, пытались убить его.

А4:Римляне либо были преданы диктатору, либо ненавидели его.

А5:Марк не был предан Цезарю.

вывести доказательство того, что Марк пытался убить Цезаря?

Видео:Урок 11. Решение задач на действия с векторамиСкачать

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

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

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

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

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

Видео:Двойственные функции ПрактикаСкачать

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

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

Видео:✓ Обратная функция | матан #024 | Борис ТрушинСкачать

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

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

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

Видео:Теория вероятностей | Математика TutorOnlineСкачать

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

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

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

Видео:21-3 Базисы булевых функцийСкачать

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

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

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

Видео:Взаимное расположение прямых на плоскости. 7 класс.Скачать

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

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

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

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

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

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

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

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

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