Как упрощать логические функции

Логическое выражение: построение и упрощение

Главная задача логики – выяснить, является ли некоторое утверждение ложным или его можно считать истинным. Для этого было изобретено несколько методов. Разработаны способы определения того, истина это или ложь, на основе других высказываний и их атрибутов. Логическое выражение – базовое понятие науки, и его параметры определяют, какие операции могут быть совершены.

Общие термины

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

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

Логические выражения в программировании

Наиболее применима логика в программировании. На примере языка Паскаль можно выделить наиболее важные операции, используемые на практике:

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

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

Основа науки

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

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

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

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

Логика выделяет ключевые операции, именуемые:

Конъюнкция

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

Источник

Как упрощать логические функции

Тема 3. Основы математической логики 1. Логические выражения и логические операции.
2. Построение таблиц истинности и логических функций.
3. Законы логики и преобразование логических выражений.
Лабораторная работа № 3. Основы математической логики.

3. Законы логики и правила преобразования логических выражений

А = .

для логического сложения: А Ú B = B Ú A;

Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

для логического сложения: (А Ú B) Ú C = A Ú (B Ú C);

для логического умножения:(A & B) & C = A & (B & C).

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

для логического умножения:(A & B) Ú C = (A Ú C) & (B Ú C).

Закон определяет правило выноса общего высказывания за скобку.

для логического сложения: = & ;

для логического умножения: = Ú

для логического сложения: А Ú A = A;

для логического умножения:A & A = A.

Закон означает отсутствие показателей степени.

для логического умножения:A & 1 = A, A & 0 = 0.

A & = 0.

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

A Ú = 1.

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

для логического умножения:A & (A Ú B) = A.

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

Нарушения законов логики приводят к логическим ошибкам и вытекающим из них противоречиям.

Пример 1. Упростить формулу (А Ú В) & (А Ú С).

Таким образом, мы доказали закон дистрибутивности.

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

Решение:

Источник

Упрощение логических выражений

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

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

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

Сущность закона исключенного третьего состоит в том, что каждое логическое выражение при любых условиях является истинным, либо ложным. Если A=1, тогда A=0, а также наоборот. Конъюнкция данных величин всегда равняется 0, дизъюнкция равна 1.

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

Сочетательный и переместительный законы имеют такой же вид, как в математике. Аналогия с привычной всем классической алгеброй.

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

Используем закон повторение, гласящий, что A⋅A=A,

A+A⋅B=A⋅(1+B)=A⋅1=A, следовательно, (A+B)⋅(A+C)=A+B⋅C.

Мы доказали равенство.

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

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

Упрощения логических выражений в примерах

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

Примеры упрощения логических выражений

Пример первый

Кто из рабочих, обозначенных, как A, B, C, D работает на заводе, а кто нет, если нам даны следующие условия:

Решение задачи. Обозначим несколько простых высказываний:

Сформулировав данные из условия при помощи этих простых высказываний, получим следующее:

Получаем следующую конъюнкцию: ((A+B)→C)⋅(B→C⋅D)⋅C.

После упрощения данной формулы получаем, что A равно 0, B равно 1, C равно 1, D равно 1.

Ответ: ученик A на заводе не работает, а ученики B, C, D играют.

В этом примере применено правило де Моргана, затем использован распределительный закон, после этого применен закон исключенного третьего, потом использован переместительный закон. За ним реализован закон повторения, потом опять применен переместительный закон и, наконец, использован закон поглощения.

Чтобы отыскать решения логического уравнения можно также применить упрощение логических выражений.

Нужно отыскать все решения данного уравнения

Применив правило де Моргана, получим

а затем применяем закон поглощения и получаем

Чтобы логическая сумма равнялась нулю, все слагаемые должны равняться нулю, из чего следует, что

A равно 1, B равно 0, C равно 0, D равно 0.

Источник

Упрощение логических выражений

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

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

Обозначим: X – логическое высказывание, – инверсия, & – конъюнкция, – дизъюнкция, – импликация, – эквиваленция.

Применение основных законов логики для упрощения логических выражений.

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

Упростить логическое выражение:

1)

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

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

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

2)

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

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

Воспользуемся операцией переменной с ее инверсией.

3)

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

Раскроем инверсию по правилу де Моргана, избавимся от инверсии по закону двойного отрицания.

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

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

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

4)

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

В выражении присутствует импликация. Сначала преобразуем импликацию .

Воспользуемся правилом де Моргана, затем законом двойного отрицания, затем раскроем скобки.

Применим закон идемпотенции и перегруппируем логические слагаемые.

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

Воспользуемся операцией с константами.

5)

Рассмотрим 3 способа упрощения этого логического выражения.

1 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.

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

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

Воспользуемся законом идемпотенции.

2 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.

Воспользуемся законом склеивания

Воспользуемся операцией переменной с ее инверсией.

3 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.

Повторим второй сомножитель , что разрешено законом идемпотенции.

Сгруппируем два первых и два последних сомножителя.

Воспользуемся законом склеивания

6)

Рассмотрим 2 способа упрощения этого логического выражения.

1 способ. Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.

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

2 способ. Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.

Введем вспомогательный логический сомножитель

Сгруппируем 1 и 4, 2 и 3 логические слагаемые. Вынесем общие логические множители за скобки.

Воспользуемся операцией с константами и операцией переменной с ее инверсией.

Получили два логических выражения:

Теперь построим таблицы истинности и посмотрим, правильно ли упрощено логическое выражение

X	Y	Z
0	0	0	0	0	0	0
0	0	1	0	0	0	0
0	1	0	0	0	0	0
0	1	1	0	1	0	1
1	0	0	1	0	0	1
1	0	1	1	0	1	1
1	1	0	0	0	0	0
1	1	1	0	0	1	1

X	Y	Z
0	0	0	1	0	0	0
0	0	1	1	0	0	0
0	1	0	0	0	0	0
0	1	1	1	0	1	1
1	0	0	1	1	0	1
1	0	1	1	1	0	1
1	1	0	0	0	0	0
1	1	1	1	1	0	1

X	Y	Z
0	0	0	0	0	0
0	0	1	0	0	0
0	1	0	0	0	0
0	1	1	0	1	1
1	0	0	1	0	1
1	0	1	1	0	1
1	1	0	0	0	0
1	1	1	0	1	1

X	Y	Z
0	0	0	0	0	0
0	0	1	0	0	0
0	1	0	0	0	0
0	1	1	1	1	1
1	0	0	1	1	1
1	0	1	1	1	1
1	1	0	0	0	0
1	1	1	1	1	1

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

Источник