Меню

A bvc построить таблицу истинности

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

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

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

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

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

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

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

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

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

Булева функция f(x1, x2, . xn) — это любая функция от n переменных x1, x2, . xn, в которой её аргументы принимают одно из двух значений: либо 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
1 1 1 1
1 1 1 1 1
1 1 1 1
1 1 1 1 1 1

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

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

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

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

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

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

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

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

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

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

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

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

Так что если Вам нужно написать программу на C/C++, C#, Pascal или Python — мы с радостью поможем с этим!

В том числе мы занимаемся репетиторством по информатике и программированию, а также готовим к ОГЭ и ЕГЭ!

  • Более 750 выполненных заказов;
  • Более 100 отзывов;
  • Качественное решение
  • Короткие сроки и привлекательные цены
  • Различные акции и скидки

Programforyou — позвольте нам писать код для вас и вы получите качественное решение в короткие сроки по привлекательной цене!

источник

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

В цифровой схемотехнике цифровой сигнал – это сигнал, который может принимать два значения, рассматриваемые как логическая “1” и логический “0”.

Логические схемы реализуются на логических элементах: “НЕ”, “И”, “ИЛИ”, “И-НЕ”, “ИЛИ-НЕ”, “Исключающее ИЛИ” и “Эквивалентность”. Первые три логических элемента позволяют реализовать любую, сколь угодно сложную логическую функцию в булевом базисе. Мы будем решать задачи на логические схемы, реализованные именно в булевом базисе.

Для обозначения логических элементов используется несколько стандартов. Наиболее распространёнными являются американский (ANSI), европейский (DIN), международный (IEC) и российский (ГОСТ). На рисунке ниже приведены обозначения логических элементов в этих стандартах (для увеличения можно нажать на рисунок левой кнопкой мыши).

На этом уроке будем решать задачи на логические схемы, на которых логические элементы обозначены в стандарте ГОСТ.

Задачи на логические схемы бывают двух видов: задача синтеза логических схемы и задачи анализа логических схем. Мы начнём с задачи второго типа, так как в таком порядке удаётся быстрее научиться читать логические схемы.

Чаще всего в связи с построением логических схем рассматриваются функции алгебры логики:

  • трёх переменных (будут рассмотрены в задачах анализа и в одной задаче синтеза);
  • четырёх переменных (в задачах синтеза, то есть в двух последних параграфах).

Рассмотрим построение (синтез) логических схем

  • в булевом базисе “И”, “ИЛИ”, “НЕ” (в предпоследнем параграфе);
  • в также распространённых базисах “И-НЕ” и “ИЛИ-НЕ” (в последнем параграфе).

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

  1. Логическая схема разбивается на ярусы. Ярусам присваиваются последовательные номера.
  2. Выводы каждого логического элемента обозначаются названием искомой функции, снабжённым цифровым индексом, где первая цифра – номер яруса, а остальные цифры – порядковый номер элемента в ярусе.
  3. Для каждого элемента записывается аналитическое выражение, связывающее его выходную функцию с входными переменными. Выражение определяется логической функцией, реализуемой данным логическим элементом.
  4. Производится подстановка одних выходных функций через другие, пока не получится булева функция, выраженная через входные переменные.

Пример 1. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.

Решение. Разбиваем логическую схему на ярусы, что уже показано на рисунке. Запишем все функции, начиная с 1-го яруса:

Теперь запишем все функции, подставляя входные переменные x, y, z :

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

Таблица истинности для данной логической схемы:

x y z f
1 1 1 1 1 1 1
1 1 1
1 1 1
1 1
1 1 1
1 1
1 1
1 1

Пример 2. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.

Пример 3. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.

Пример 4. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.

Решение. Разбиваем логическую схему на ярусы. Запишем все функции, начиная с 1-го яруса:

Теперь запишем все функции, подставляя входные переменные x, y, z :

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

Таблица истинности для данной логической схемы:

x y z f
1 1 1 1 1
1 1 1 1
1 1 1 1
1
1 1 1 1
1 1 1
1 1 1
1 1

Пример 5. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.

Решение. Разбиваем логическую схему на ярусы. Структура данной логической схемы, в отличие от предыдущих примеров, имеет 5 ярусов, а не 4. Но одна входная переменная – самая нижняя – пробегает все ярусы и напрямую входит в логический элемент в первом ярусе. Запишем все функции, начиная с 1-го яруса:

Теперь запишем все функции, подставляя входные переменные x, y, z :

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

Таблица истинности для данной логической схемы:

x y z f
1 1 1 1 1 1
1 1 1 1 1
1 1 1 1
1 1 1
1 1 1 1 1
1 1 1 1
1 1 1
1 1

Разработка логической схемы по её аналитическому описанию имеет название задачи синтеза логической схемы.

Каждой дизъюнкции (логической сумме) соответствует элемент “ИЛИ”, число входов которого определяется количеством переменных в дизъюнкции. Каждой конъюнкции (логическому произведению) соответствует элемент “И”, число входов которого определяется количеством переменных в конъюнкции. Каждому отрицанию (инверсии) соответствует элемент “НЕ”.

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

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

x y f
1 1
1
1 1

Решение. Разбираем таблицу истинности для логической схемы. Определяем функцию, которая получится на выходе схемы и промежуточные функции, которые на входе принимают аргументы x и y . В первой строке результатом реализации выходной функции при том, что значения входных переменных равны единицам, должен быть логический “0”, во второй строке – при разных значениях входных переменных на выходе тоже должен быть логический “0”. Поэтому нужно, чтобы выходная функция была конъюнкцией (логическим произведением).

Читайте также:  Как подготовить к зиме хризантемы в саду

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

1
1 1 1
1

Для построения логической схемы необходимо элементы, реализующие логические операции, указанные в выходной функции, располагать в порядке, заданной этой функцией. Из выражения видно, что понадобятся 3 схемы “НЕ”, две двухвходовых схемы “И” и одна двухвходовая схема “ИЛИ”. В соответствии с выходной функцией получаем следующую логическую схему:

А теперь очередь дошла до функций алгебры логики четырёх переменных. Сначала выполним синтез логической схемы в булевом базисе.

Пример 7. Построить в булевом базисе логическую схему, реализующую функцию алгебры логики

Решение. Для построения логической схемы потребуются 4 схемы “НЕ”, одна трёхвходовая схема “И”, 2 двухвходовые схемы “И” и одна трёхвходовая схема “ИЛИ”. В соответствии с этим получаем следующую логическую схему:

Часто для сокращения числа микросхем используют элементы “И-НЕ” или/и “ИЛИ-НЕ”. Рассмтрим примеры, как построить схему, реализующую ту же функцию, что в предыдущем примере, но, сначала в базисе “И-НЕ”, а затем в базисе “ИЛИ-НЕ”.

Пример 8. Построить в базисе “И-НЕ” логическую схему, реализующую функцию алгебры логики .

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

Для построения логической схемы потребуются 8 схем “И-НЕ”. Получаем следующую логическую схему:

Пример 9. Построить в базисе “ИЛИ-НЕ” логическую схему, реализующую функцию алгебры логики .

источник

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

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

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

Равносильными называются логические выражения, последние столбцы таблиц истинности которых совпадают. Равносильность обозначается с помощью знака $«=»$.

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

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

Определяют количество строк: кол-во строк = $2^n + 1$ (для строки заголовка), $n$ – количество простых выражений. Например, для функций двух переменных существует $2^2 = 4$ комбинации наборов значений переменных, для функций трех переменных – $2^3 = 8$ и т.д.

Определяют количество столбцов: кол-во столбцов = кол-во переменных + кол-во логических операций. При определении количества логических операций учитывают также порядок их выполнения.

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

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

Составить таблицу истинности логического выражения $D=\bar \vee (B \vee C)$.

Определим количество строк:

Количество простых выражений – $n=3$, значит

Определим количество столбцов:

Количество логических операций и их последовательность:

Заполним таблицу, учитывая таблицы истинности логических операций.

Задай вопрос специалистам и получи
ответ уже через 15 минут!

По данному логическому выражению построить таблицу истинности:

Определим количество строк:

Количество простых выражений – $n=3$, значит

Определим количество столбцов:

Количество логических операций и их последовательность:

  1. отрицание ($\bar$);
  2. дизъюнкция, т.к. она находится в скобках ($A \vee B$);
  3. конъюнкция ($(A\vee B)\bigwedge \overline$);
  4. отрицание, которое обозначим $F_1$ ($\overline<(A\vee B)\bigwedge \overline>$);
  5. дизъюнкция ($A \vee C$);
  6. конъюнкция ($(A\vee C)\bigwedge B$);
  7. отрицание, которое обозначим $F_2$ ($\overline<(A\vee C)\bigwedge B>$);

Заполним таблицу, учитывая таблицу истинности логических операций.

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

По данной таблице истинности некоторой логической функции $Y(A,B)$ cоставить соответствующую логическую функцию.

  1. Значение функции равно $1$ в $1$-й и $3$-й строках таблицы.
  2. Поскольку имеем $2$ строки, получим дизъюнкцию двух элементов:

  • Каждое логическое выражение в этой дизъюнкции запишем как конъюнкцию аргументов функции $A$ и $B$: $\left(A\wedge B\right)\vee \left(A\wedge B\right)$
  • В случае, когда значение в соответствующей строке таблицы равно $0$, запишем этот аргумент с отрицанием, получим искомую функцию:\[Y\left(A,B\right)=\left(\overline\wedge \overline\right)\vee \left(A\wedge \overline\right).\]
  • Так и не нашли ответ
    на свой вопрос?

    Просто напиши с чем тебе
    нужна помощь

    источник

    19 мая Выпустили приложение для телефона —

    15 мая Повтори весь материал ЕГЭ на курсе Умскул и прибавь к результату 20 баллов.

    − Учитель Думбадзе
    из школы 162 Кировского района Петербурга.

    ЧИТАТЬ ВСЕ НОВОСТИ декабря На нашем сайте размещён курс русского языка Людмилы Великовой.

    3 мая Ещё один вариант досрочного ЕГЭ по математике.

    14 апреля Вариант резервного дня ЕГЭ по математике.

    13 апреля Вариант досрочного ЕГЭ по физике.

    12 апреля Вариант досрочного ЕГЭ по информатике.

    17 апреля Кратко о специальной теории относительности.

    Наша группа ВКонтакте
    Мобильные приложения:

    Составьте таблицу истинности для логической функции

    в которой столбец значений аргумента А представляет собой двоичную запись числа 27, столбец значений аргумента В — числа 77, столбец значений аргумента С — числа 120. Число в столбце записывается сверху вниз от старшего разряда к младшему(включая нулевой набор). Переведите полученную двоичную запись значений функции X в десятичную систему счисления.

    Запишем уравнение, используя более простые обозначения операций:

    1) это выражение с тремя переменными, поэтому в таблице истинности будет строчек; следовательно, двоичная запись чисел, по которым строятся столбцы таблицы А, В и С, должна состоять из 8 цифр

    2) переведем числа 27, 77 и 120 в двоичную систему, сразу дополняя запись до 8 знаков нулями в начале чисел

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

    А В С X
    1 1
    1
    1 1
    1 1 1
    1
    1
    1 1

    4) заполняем столбцы таблицы:

    А В С X
    1 1 1
    1 1 1 1
    1 1 1 1 1
    1 1 1 1
    1 1 1 1 1 1 1
    1 1 1
    1 1 1
    1 1 1 1 1 1

    значение равно 1 только в тех строчках, где А = В

    значение равно 1 в тех строчках, где либо В либо С = 1

    значение равно 0 только в тех строчках, где А = 1 и В + С = 0

    значение — это инверсия предыдущего столбца (0 заменяется на 1, а 1 – на 0)

    результат Х (последний столбец) — это логическая сумма двух столбцов и

    5) чтобы получить ответ, выписываем биты из столбца Х сверху вниз:

    6) переводим это число в десятичную систему:

    источник

    Они могут принимать значения «истина» или «ложь» (1 или 0). Для функции, содержащей две переменные, наборов значений переменных всего четыре:

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

    1. Конъюнкция (логическое умножение) – сложное логическое выражение, которое является истинным только в том случае, когда истинны оба входящих в него простых выражения.

    Обозначение:

    2. Дизъюнкция (логическое сложение) – это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно, если оба простых логических выражения ложны.

    Обозначение:

    3. Импликация (логическое следствие) – это сложное логическое выражение, которое является ложным тогда и только тогда, когда условие истинно, а следствие ложно.

    Обозначение:

    4. Эквиваленция – это сложное логическое высказывание, которое является истинным только при одинаковых значениях истинности простых выражений, входящих в него.

    Обозначение:

    5. Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное – истинным.

    Обозначение:

    6. Штрих Шеффера – операция, отрицающая конъюнкцию, т.е. значение ложно тогда и только тогда, когда оба простых выражения истинны.

    Обозначение:

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

    Обозначение:

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

    1. Инверсия
    2. Конъюнкция
    3. Дизъюнкция
    4. Импликация
    5. Эквиваленция
    6. Штрих Шеффера
    7. Стрелка Пирса

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

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

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

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

    I –

    II –

    III –

    IV –

    V –

    VI –

    источник

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

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

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

    • 1. инверсия;
    • 2. конъюнкция;
    • 3. дизъюнкция;
    • 4. импликация и эквивалентность.

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

    Предлагается следующий алгоритм построения таблицы истинности.

    • 1. Определить количество наборов входных переменных – всевозможных сочетаний значений переменных, входящих в выражения, по формуле: Q=2n , где n – количество входных переменных. Оно определяет количество строк таблицы.
    • 2. Внести в таблицу все наборы входных переменных.
    • 3. Определить количество логических операций и последовательность их выполнения.
    • 4. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности.

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

    Способ 1. Каждый набор значений исходных переменных есть код числа в двоичной системе счисления, причем количество разрядов числа равно количеству входных переменных. Первый набор – число 0. Прибавляя к текущему числу каждый раз по 1, получаем очередной набор. Последний набор – максимальное значение двоичного числа для данной длины кода.

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

    Способ 2. Для функции от трех переменных последовательность данных можно получить следующим путем:

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

    Способ 3. Воспользоваться известной таблицей истинности для двух аргументов. Добавляя третий аргумент, сначала записать первые 4 строки таблицы, сочетая их со значением третьего аргумента, равным 0, а затем еще раз записать эти же 4 строки, но теперь уже со значением третьего аргумента, равным 1. В результате в таблице для трех аргументов окажется 8 строк:

    Например, построим таблицу истинности для логической функции:

    Количество входных переменных в заданном выражении равно трем (A,B,C). Значит, количество входных наборов Q=2 3 =8.

    Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C, промежуточных результатов и (B V C), а также искомого окончательного значения сложного арифметического выражения :

    • 0 0 0 1 0 0
    • 0 0 1 1 1 1
    • 0 1 0 1 1 1
    • 0 1 1 1 1 1
    • 1 0 0 0 0 0
    • 1 0 1 0 1 0
    • 1 1 0 0 1 0
    • 1 1 1 0 1 0
    • 7.4. Логические функции и их преобразования. Законы логики

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

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

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

    Пример 2. Минимизировать функцию

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

    Пример 3. Найти отрицание следующего высказывания: “Если урок будет интересным, то никто из учеников (Миша, Вика, Света) не будет смотреть в окно”.

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

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

    • 1) “Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал”;
    • 2) “Если Иванов не участвовал, то Сидоров не участвовал”.

    I – “Иванов участвовал в преступлении”;

    P – “Петров участвовал в преступлении”;

    S – “Сидоров участвовал в преступлении”.

    Запишем посылки в виде формул:

    Проверим результат, используя таблицу истинности:

    Ответ: Иванов участвовал в преступлении.

    Построение логической функции по ее таблице истинности

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

    Рассмотрим строки, где значение истинности функции Z истинно (Z=1). Функцию для этой таблицы истинности можно составить следующим образом: Z(X,Y) = (¬ X& ¬Y)V(X& ¬Y).

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

    Z(X,Y) ((¬X& ¬Y) VX)&(( ¬X&Y)V ¬Y) (XV( ¬X& ¬Y)) &( ¬YV(¬X&¬Y)) ((XV¬X)&(XV ¬Y))&(( Y¬V ¬X)&( ¬YV ¬Y)) (1&(XV ¬Y))&(( ¬YV ¬X)& ¬Y) (XV ¬Y)&(( ¬YV ¬X)& ¬Y).

    Проверьте полученную формулу: составьте таблицу истинности для функции Z(X,Y).

    Запишите правила конструирования логической функции по ее таблице истинности:

    • 1. Выделить в таблице истинности те строки, в которых значение функции равно 1.
    • 2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.
    • 3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.
    • 4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент мы берем с отрицанием.

    источник

    Adblock
    detector