Меню

Пусть таблица истинности некоторой булевой функции имеет вид

Определить логическую функцию, соответствующую КНФ

Здравствуйте! Помогите пожалуйста решить такую задачу, желательно с подробным решением.

Пусть таблица истинности некоторой булевой функции имеет вид:
х y F(x,y)
0 0 1
0 1 1
1 0 0
1 1 1

Определить логическую функцию F(x,y), соответствующую КНФ.

Помощь в написании контрольных, курсовых и дипломных работ здесь.

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

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

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

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

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Вычислить, вводя соответствующую функцию
Вычислить, вводя соответствующую функцию y = Tg(Tg(x))-Ctg(Ctg(x))

Подобрать соответствующую функцию и найти ее экстремум
Найти радиус основания и высоту конуса наименьшего объема, описанного около шара радиуса R

Минимизировать функцию в классах ДНФ и КНФ
Минимизировать функцию методами Квайна, сочетания индексов и картой Карно в классах ДНФ и.

Разложить для КНФ по аргументу x функцию
2. Разложить для КНФ по аргументу x следующую функцию: f(x,y,z,t)=x¬y˅zt

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

Вычислить, вводя соответствующую функцию в разделе Function
Задание 2. Вычислить, вводя соответствующую функцию в разделе Function:y= arcsin(x)-arcsin^3(2x)

Источник



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

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

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

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

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

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

Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики — алгебры логики. В алгебре логики можно выделить три основные логические функции: «НЕ» (отрицание), «И» (конъюнкция), «ИЛИ» (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2 n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:

  • словесное описание – это форма, которая используется на начальном этапе проектирования имеет условное представление.
  • описание функции алгебры логики в виде таблицы истинности.
  • описание функции алгебры логики в виде алгебраического выражения: используется две алгебраические формы ФАЛ:
    а) ДНФ – дизъюнктивная нормальная форма – это логическая сумма элементарных логических произведений. ДНФ получается из таблицы истинности по следующему алгоритму или правилу:
    1) в таблице выбираются те строки переменных для которых функция на выходе =1 .
    2) для каждой строки переменных записывается логическое произведение; причём переменные =0 записываются с инверсией.
    3) полученное произведение логически суммируется.
    Fднф= X 123 ∨ Х1 x 2Х3 ∨ Х1Х2 x 3 ∨ Х1Х2Х3
    ДНФ называется совершенной, если все переменные имеют одинаковый ранг или порядок, т.е. в каждое произведение обязательно должны включаться все переменные в прямом или инверсном виде.
    б) КНФ – конъюнктивная нормальна форма – это логическое произведение элементарных логических сумм.
    КНФ может быть получена из таблицы истинности по следующему алгоритму:
    1) выбираем наборы переменных для которых функция на выходе =0
    2) для каждого набора переменных записываем элементарную логическую сумму, причём переменные =1 записываются с инверсией.
    3) логически перемножаются полученные суммы.
    Fскнф=(X1 V X2 V X3) ∧ (X1 V X2 V X 3) ∧ (X1 V X 2 V X3) ∧ ( X 1 V X2 V X3)
    КНФ называется совершенной, если все переменные имеют одинаковый ранг.

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

Рисунок1- Схема логического устройства

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

Источник

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

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

  • Определение. Булевой функцией называется n-местная функция, аргументы которой принимают значения во множестве <0, 1>и сама функция принимает значения в этом же множестве.

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

Для n=3 булеву функцию можно задать таблицей .

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

Пусть задана булева функция от трех переменных (табл.). Тогда число наборов 2 3 =8.

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

Существует ровно $2^<2^>$ различных булевых функций от n переменных. Константы 0 и 1 считают нуль-местными булевыми функциями.

Утверждение. Каждой формуле логики высказываний соответствует некоторая булева функция.

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

Решение. Поскольку n=2, различных булевых функций от двух переменных существует ровно 16 (табл.).

Источник

Пусть таблица истинности некоторой булевой функции имеет вид

Дискретная математика

2. Математическая логика

Определение. Высказывание – повествовательное утверждение, которое либо истинно либо ложно (не то и другое одновременно).

Примеры высказываний: «Тише едешь – дальше будешь», «Париж – столица Франции». Но «Как бы чего не вышло» или «Миру – мир» не являются высказываниями.

Определение. Высказывание называется простым (элементарным), если оно рассматривается как одно неделимое целое.

Определение. Сложное высказывание – высказывание, составленное из простых с помощью логических связок.

2.2 логические связки (операции) над высказываниями.

Определение. Конъюнкцией («и») высказываний P и Q называется высказывание, истинное тогда и только тогда, когда оба истинны. Обозначается или PQ .

Определение. Дизъюнкцией («или») высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба ложны. Обозначается .

Определение. Отрицанием («не») высказывания P называется высказывание, ложное тогда и только тогда, когда P истинно. Обозначается или .

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

Определение. Эквивалентностью высказываний P и Q называется высказывание истинное, когда истинностные значения P и Q совпадают, и ложное в противном случае. Обозначается или .

Определение. Неравнозначностью (сложение по модулю 2) высказываний P и Q называется высказывание истинное, когда истинностные значения P и Q различны, и ложное в противном случае. Обозначается .

2.3 Пропозициональные формулы

Рассмотрим алфавит , где , , .

Символы из называются переменными высказывания или пропозициональными переменными .

Символы из называются логическими связками .

Скобки из называются вспомогательными символами .

Определение . Пропозициональная формула определяется следующим образом:

1) пропозициональная переменная есть формула;

2) если P и Q – формулы, то Ø P , ( P & Q ), ( P Ú Q ) ,( P ® Q ) ,( P Å Q ) ,( P | Q ), ( P ¯ Q ) – формулы,

3) других формул нет.

а) внешние скобки у формул опускаются;

б) устанавливаются следующие приоритеты:

Ø – выполняется в первую очередь;

Ú , ® , Å , |, ¯ – в третью очередь.

2.4 Булевы функции. Таблицы истинности.

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

1) таблицами истинности; при этом 0 интерпретируется как «ложь», а 1 – как «истина»;
2) пропозициональными формулами.

Таблица истинностей некоторых логических связок:

2.5 Булевы функции одной переменной

Обозначение

Наименование

Константа 0

Тождественная

Отрицание

Константа 1

2.6 Булевы функции двух переменных

Обозначение

Наименование

Константа 0

Конъюнкция

Сложение

Дизъюнкция

Стрелка Пирса

Эквиваленция

Импликация

Импликация

Штрих Шеффера

Константа 1

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

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

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

2.8 Равносильные формулы. Основные равносильности

Определение . Формула называется тождественно истинной , или тавтологией , если эта формула принимает значение 1 при всех наборах значений переменных.

Определение . Формула называется тождественно ложной , или противоречием , если эта формула принимает значение 0 при всех наборах значений переменных.

2.9 Основные тавтологии

Закон исключенного третьего

Цепное рассуждение

Определение . Формулы P и Q называются равносильными (обозначается ), если при любых значениях переменных значение формулы P совпадает со значением Q .

2.10 Основные равносильности

Коммутативность и

Ассоциативность и

Дистрибутивность и

Идемпотентность и

Законы исключенного третьего и противоречия

Законы де Моргана

Законы поглощения

Правило склеивания

Закон двойного отрицания

Коммутативность

Ассоциативность

Дистрибутивность и

Замечание . Здесь P , Q и R —пропозициональные формулы.

2.11 Понятие двойственной функции

Определение . Функцией, двойственной к булевой функции , называется функция .

Определение . Функция называется самодвойственной , если .

Теорема . ( Принцип двойственности .) Пусть ,…, и — булевы функции и пусть = — сложная булева функция. Тогда

Следствие . Пусть P и Q —формулы. Если , тогда .

Принцип двойственности позволяет получать из доказанных равносильностей целый ряд новых. Кроме того, СКНФ( f )= .

2.12 Некоторые двойственные функции

Замечание . .

2.13 Элементарные канонические формы

Определение . Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более 1 раза.

Определение . Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более 1 раза.

2.14 Нормальные формы формул

Определение . Дизъюнктивной нормальной формой (Д.Н.Ф.) называется произвольная дизъюнкция элементарных конъюнкций.

Определение . Конъюнктивной нормальной формой (К.Н.Ф.) называется произвольная конъюнкция элементарных дизъюнкций.

Определение . К.Н.Ф. называется совершенной и обозначается С.К.Н.Ф. , если каждая переменная входит в каждую элементарную дизъюнкцию ровно один раз с отрицанием или без.

Определение . Д.Н.Ф. называется совершенной и обозначается С.Д.Н.Ф , если каждая переменная входит в каждую элементарную конъюнкцию ровно один раз с отрицанием или без.

Пример: – Д.Н.Ф; – С.Д.Н.Ф.

Теорема . Любая логическая функция кроме 0 имеет единственную С.Д.Н.Ф: .

Теорема . Любая логическая функция кроме 1 имеет единственную С.К.Н.Ф: .

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

Записать ее С.Д.Н.Ф. и С.К.Н.Ф.

2.15 Приведение формул к нормальным формам

Любую логическую формулу (кроме 0) можно привести к С.Д.Н.Ф. следующим образом:

Все не булевские операции заменить на булевские (&, Ú , Ø ) c помощью равносильностей:

Все отрицания «спустить» до переменных с помощью законов де Моргана.

Раскрыть скобки (дистрибутивность, ассоциативность).

Удалить лишние конъюнкции, повторения переменных в конъюнкциях и константы.

Для приведения к С.Д.Н.Ф:

Расщепить те конъюнкции, которые содержат не все переменные.

2.16 Минимизация д.н.ф.

Д.Н.Ф, содержащую минимальное число вхождений переменных, будем считать минимальной .

Приведем 2 наиболее простых метода минимизации Д.Н.Ф. функции:

Группировка: элементарные конъюнкции , в ДНФ группируются в пары так, что после вынесения за скобку общего множителя K подформула имела вид или . Далее заменяем на эквивалентную ей конъюнкцию K .

Метод Блейка состоит в применении двух правил:

а) обобщенное склеивание – первое правило. С помощью формулы производим операцию обобщенного склеивания в Д.Н.Ф. пока это возможно. Для этого в Д.Н.Ф. отыскиваем подформулы вида и добавляем к ним . На этом этапе формула усложняется.

б) поглощение – второе правило. Оно основано на равенстве

Находим в Д.Н.Ф. конъюнкции с минимальным числом сомножителей и все конъюнкции, их содержащие, вычеркиваем.

Разумно в Д.Н.Ф. сначала применить метод группировки (как более простой), а затем метод Блейка.

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

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

Определение Логическая функция, представленная над базисом называется многочленом Жегалкина. Он имеет вид:

2.18 Функционально замкнутые классы функций

Ведем следующие классы Поста:

= – Класс функций, сохраняющих 0.

= – Класс функций, сохраняющих 1.

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

= – Класс линейных функций.

= – Класс монотонных функций.

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

Таблица принадлежности функциональным классам основных булевых функций:

Источник

СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице

СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице
  1. Услуги проектирования
  2. Алгебра логики [Г.И. Просветов, Е.А. Фоминых, Ф.Г. Кораблёв]
  3. СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице

СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице

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

  • полная, если в неё каждая переменная < или её отрицание >входит ровно 1 раз;
  • монотонная, если она не содержит отрицаний переменных.

ДНФ — нормальная форма, в которой булева функция имеет вид дизъюнкции нескольких простых конъюнктов.

Пример ДНФ: $f(x,y,z) = (x \land y) \lor (y \land \neg < z >)$

СДНФ — это такая ДНФ, которая удовлетворяет условиям:

  • в ней нет одинаковых простых конъюнкций
  • каждая простая конъюнкция полная

Пример СДНФ: $f(x,y,z) = (x \land \neg < y >\land z) \lor (x \land y \land \neg < z >)$

Теорема: Для любой булевой функции $f(\vec < x >)$, не равной тождественному нулю (), существует СДНФ, ее задающая.

Для любой булевой функции выполняется следующее соотношение, называемое разложением Шеннона.

$f(\vec < x >) = \neg x_i \wedge f(x_1, \dots ,x_ < i-1 >,0,x_ < i+1 >, \dots ,x_n) \vee x_i \wedge f(x_1, \dots ,x_ < i-1 >,1,x_ < i+1 >, \dots ,x_n)$

Данное соотношение легко проверить подстановкой всевозможных значений $x_i$ < $0$ и $1$ >. Эта формула позволяет выносить $x_i$ за знак функции. Последовательно вынося $x_1$, $x_2$. $x_n$ за знак $f(\vec < x >)$, получаем следующую формулу :

$ f(\vec < x >) = \neg x_1 \wedge \neg x_2 \wedge . \wedge \neg x_ < n-1 >\wedge \neg x_n \wedge f(0,0. 0,0)

$\neg x_1 \wedge \neg x_2 \wedge . \wedge \neg x_ < n-1 >\wedge x_n \wedge f(0,0. 0,1)

x_1 \wedge x_2 \wedge . \wedge x_ < n-1 >\wedge \neg x_n \wedge f(1,1. 1,0)

$ $x_1 \wedge x_2 \wedge . \wedge x_ < n-1 >\wedge x_n \wedge f(1,1. 1) $

Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от $n$ переменных мы имеем < < < $2^ < n >$ > > > конъюнктов. Каждый из них соответствует значению функции на одном из < < < $2^ < n >$ > > > возможных наборов значений $n$ переменных. Если на некотором наборе $f(\vec < x >)=0$, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же $ f(\vec < x >)=1$, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.

Алгоритм построения СДНФ по таблице истинности

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

Пример построения СДНФ для медианы

В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.

x y z $\langle x,y,z \rangle$
1
1 1
1 1 1
1
1 1 1
1 1 1
1 1 1 1

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

x y z $ \langle x,y,z \rangle $
1
1
1 1 1 $(\neg < x >\land y \land z)$
1
1 1 1 $(x \land \neg < y >\land z)$
1 1 1 $(x \land y \land \neg < z >)$
1 1 1 1 $(x \land y \land z)$

Все полученные конъюнкции связываем операциями дизъюнкции. $ \langle x,y,z \rangle = (x \land y \land z) \lor (\neg < x >\land y \land z) \lor (x \land \neg < y >\land z) \lor (x \land y \land \neg < z >)$

Примеры СДНФ для некоторых функций

Стрелка Пирса: $x \downarrow y = (\neg < x >\land \neg < y >)$

Исключающее или: $x \oplus y \oplus z = (\overline < x >\land \overline < y >\land z) \lor (\overline < x >\land y \land \overline < z >) \lor (x \land \overline < y >\land \overline < z >) \lor (x \land y \land z)$

Совершенной дизъюнктивной нормальной формой формулы $A(x_1,x_2,…,x_n)$ называется ДНФ, обладающая следующими свойствами:

а > в ней нет одинаковых дизъюнктивных элементов;

б > ни одна элементарная конъюнкция не содержит двух одинаковых высказываний;

в > ни какая элементарная конъюнкция не содержит высказывание вместе с ее отрицанием;

г > в каждой элементарной конъюнкции содержится либо $X_i$, либо $\overline < X >_i$, где $i = 1, n$.

Условие а > – г > являются необходимыми и достаточными для того, чтобы ДНФ стала СДНФ. В свою очередь эти условия дают возможность составить алгоритм получения СДНФ из ДНФ:

1) если какая-нибудь элементарная конъюнкция не содержит высказывание $X_i$, то заменим выражением $B\wedge (X_i\vee \overline < X >_i) \equiv (B\wedge X_i)\vee (B\wedge \overline < X >_i)$;

2) если в полученном выражении окажутся одинаковые элементарные конъюнкции, то лишние опускаются;

3) если в некоторых элементарных конъюнкциях окажутся одинаковые высказывания, то лишние опускаются;

4) удаляем элементарные конъюнкции, в которых содержатся высказывания вместе с их отрицанием.

Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.

Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.

Формула называется дизъюнктивной нормальной формой < ДНФ >, если она является дизъюнкцией неповторяющихся элементарных конъюнкций. ДНФ записываются в виде: $A_1\vee A_2\vee . \vee A_n$ , где каждое $A_n$ — элементарная конъюнкция.

Формула $A$ от $k$ переменных называется совершенной дизъюнктивной нормальной формой < СДНФ >, если:

$A$ является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция $k$ переменных $x_1,x_2,…,x_k$, причем на $i$-м месте этой конъюнкции стоит либо переменная $x_i$ либо ее отрицание;

Все элементарные конъюнкции в такой ДНФ попарно различны.

Например: $A = x_1 \wedge$ НЕ $x_2 \vee x_1 \wedge x_2$

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

Она является примером однозначного представления булевой функции в виде формульной < алгебраической >записи.

Теорема о СДНФ: Пусть $f(x_1 x_2, …, x_n)$ – булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию $f$.

Алгоритм построения СДНФ по таблице истинности:

  • В таблице истинности отмечаем наборы переменных, на которых значение функции $f = 1$.
  • Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае – ее отрицание.
  • Все полученные конъюнкции связываем операциями дизъюнкции.

Далее:

Механические приложения двойного интеграла

Замена переменных в двойном интеграле. Двойной интеграл в полярных координатах

Векторное поле

Поверхностный интеграл первого рода и его свойства

Булевы функции от $n$ переменных

Односторонние и двусторонние поверхности. Ориентация поверхности

Вычисление объёмов

Класс $T_0$. Теорема о замкнутости класса $T_0$

Формула Гаусса — Остроградского

Замена переменных в тройном интеграле

Теорема о предполных классах

Определение тройного интеграла. Теорема существования тройного интеграла

Несобственные интегралы от неограниченной функции

Теорема об алгоритме распознавания полноты

Огравление $\Rightarrow $

Источник

Читайте также:  Таблицы для уроков сольфеджио
Adblock
detector