Упрощение выражений алгебра логики онлайн: Математическая логика · oнлайн с подробным объяснением

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

Похожие презентации:

Законы математической логики

Логика высказываний

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

Основы логики. Таблица истинности. Равносильные логические выражения

Математическая логика. Логика высказываний

Математическая логика. Логические операции и высказывания

Алгебра логики

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

Математическая логика и теория алгоритмов

Логические основы компьютера. Формы человеческого мышления. Формальная логика

1. Законы и правила математической логики

Упрощение сложных
высказываний
Устимкина Л.И.
900igr.net
1

2. Основные законы алгебры логики

1
А≡ А
(А≡А)
Закон тождества
2
A&Ā=0
(А ∙ Ā= 0)
Закон непротиворечия
3
A v Ā=l
(A+ Ā= 1)
Закон исключающего третьего
4
_
Ā=A
Закон двойного отрицания
5
А& 0= 0
Av0=A
А∙ 0=0
A+0=A
6
А& 1= A
Аv 1= 1
А∙ 1= A
А+ 1= 1
7
А& A= A
Аv A= A
А ∙A= A
А+ A= A
8
Аv Ā= 1
А+ Ā= 1
9
______ _
(A→B)=A& B
_____ _
(A→B)=A∙B
10
A→B=Ā v B
A→B=Ā+B
11
A&(A v B)=A
A∙(A+B)=A
Устимкина Л. И.
Закон Моргана
Закон поглощения
2
Основные законы алгебры логики
A+A∙B = A
Закон поглощения
12
A v A&B = A
13
Ā&(AvB) = Ā&B
14
AvĀ&B = AvB
A+Ā∙B = A+B
15
(AvB) vC =Av(BvC)
(A+B)+C=A+(B+C)
Правило
(A&B)&C = A&(B&C)
(A∙B)∙C = A∙(B∙C)
ассоциативности
(A&B) v (A&C) = A &(B vC)
(A∙B) +(A∙C) =
A∙(B+C)
Правило
16
Ā∙(A+B) = Ā∙B
дистрибутивности
17
AvA = AA&A = A
A+A = AA∙A = A
Правило
идемпотентности
18
A v B=B v AA&B=B&A
A+B=B+AA∙B=B∙A
Правило
коммутативности
19
___
A≡B = A & B v A& В = (Ā+B) &(A+ B)
Устимкина Л.И.
3
МОРГАН Огастес де
(Morgan Augustus de)
Морган Огастес (Августус) де (27.6.1806-18.3. 1871)-шотландский математик и логик. Секретарь
Королевcкого астрономического общества (1847г.), член Лондонского королевского общества.
Первый президент Лондонского математического общества. Родился в Мадуре (Индия). Учился в
Тринити-колледж (в Кембридже). Профессор математики в университетском колледже в Лондоне.
Основные труды по алгебре, математическому анализу и математической логике. В теории рядов
описал логарифмическую шкалу для критериев сходимости; занимался теорией расходящихся рядов.
Один из основателей формальной алгебры. Продолжая работы Дж. Пикока, Морган в 1841-1847гг.
опубликовал ряд работ по основам алгебры. В трактате «Формальная логика или исчисление выводов
необходимых и возможных» (1847г.), Морган некоторыми своими положениями опередил Дж. Буля.
Позднее Морган успешно изучал логику отношений — область, не охваченную исследованиями
предшественников. В книге «Тригонометрия и двойная алгебра» (1849г.) развил мысль У. Гамильтона
о распространении идей символической алгебры на исчисление комплексных величин. Благодаря
этому комплексные величины были строго обоснованы не только геометрически, но и
алгебраически. Написал много исторических работ, в частности книгу «Бюджет парадоксов» (1872г. ).
Большой вклад внес также в дедуктивную логику вообще и математическую в частности.
Лондонское математическое общество учредило медаль им. О. Моргана.
Устимкина Л.И.
4

5. Задание 1. Упростить выражение: _ X ∙ Y V X ∙ Y

Задание 1. Упростить выражение:
_
X∙YVX∙Y
Воспользуемся распределительным законом:
Х ∙(Y V Z ) =X ∙ Y V X ∙ Z
(или вынесем общий множитель за скобку)
X∙YVX∙Y=
_
X ∙(Y V Y ) =
1
Устимкина Л.И.
=Х∙1=Х
5
Задание 2. Упростите логическое выражение
_______________
_____
F= (A v B)→ (B v C).
1. Избавимся от импликации и отрицания. Воспользуемся (¬(A→B)=A& ¬ B).
Получится: ¬((AvB)→ ¬(BvC))= (AvB)& ¬ (¬(BvC)).
2. Применим закон двойного отрицания, получим:
(A v В) & ¬(¬(В v С)) = (A v В) & (B v С).
3. Применим правило дистрибутивности ((A∙B) +(A∙C) = A∙(B+C)). Получим:
(AvВ)& (B v С)= (AvB)&Bv(AvB)&C
4. Применим закон коммутативности (A&B=B&A ) и дистрибутивности (16).
Получим: (AvB)&Bv(AvB)&C = A&BvB&BvA&CvB&C.
5. Применим (А& A= A) и получим: A&BvB&BvA&CvB&C= A&BvBvA&CvB&C
6. Применим ((A&B) v(A&C) = A&(BvC) ), т.е. вынесем за скобки В.
Получим:A&BvBvA&CvB&C= B& (Av1)vA&CvB&C.
7. Применим (Аv 1= 1 ). Получим:B& (Av1) vA&CvB&C= BvA&CvB&C.
8. Переставим местами слагаемые, сгруппируем и вынесем В за скобки.
Получим:BvA&CvB&C = B& (1vC)vA&C.
9. Применим (Аv 1= 1 ) и получим ответ: B&(1vC)vA&C=BvA&C.
Устимкина Л.И.
6
IV. Закрепление изученного
№1
Упростите выражение:
1. F = ¬ (A&B) v ¬ (BvC).
2. F = (A→B) v (B→A).
3. F = A&CvĀ&C.
4. F = Av Bv CvAvBvC
Ответы:
1. F = ¬ (A&B) v ¬ (BvC) = Av B.
2. F= (A→B) v (B→A) = 1.
3. F = A&CvĀ&C=C.
4. F = Av Bv CvAvBvC=1.
Устимкина Л.И.
7
№2
Упростите выражение:
1. F = ¬(X&Yv ¬(X&Y)).
2. F = X&¬ ( YvX).
3. F = (XvZ) & (Xv Z) & ( YvZ).
Ответы:
1. F = ¬(X&Yv ¬(X&Y)) = 0.
2. F = X&¬ ( YvX) = X&Y.
3. F = (XvZ) & (Xv Z) & ( YvZ)
=X&( YvZ).
Устимкина Л.И.
8
Домашняя работа
I. Упростите логические выражения:
1. F = Av ( A&B).
2. F = A& ( AvB).
3. F = (AvB) & ( BvA) & ( CvB).
4. F = (1V (AvB)) V ((AvC) &1).
II. Дана следующая логическая схема. Упростите ее,
используя минимальное количество вентилей.
A
B
&
¬
V
C
&
V
¬
&
¬
III. Как составить расписание.
При составлении расписания
учителя высказали следующие
пожелания: учитель физики хочет
иметь первый и второй урок;
учитель химии — первый или третий;
учитель информатики — второй или
третий. Предложите возможные
варианты расписания.
Устимкина Л.И.
9

English     Русский Правила

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

Шаг 1. Заменить операцию на её выражение через

И, ИЛИ и НЕ:

A B A B A B

Шаг 2. Раскрыть инверсию сложных выражений по формулам де Моргана:

A B A B, A B A B

Шаг 3. Используя законы логики, упрощать выражение, стараясь применять закон исключения третьего.

21

Синтез логических выражений

A B X

0 0 1 A B

0 1 1 A B 1 0 0

1 1 1 A B

Шаг 1. Отметить строки в таблице, где X = 1.

Шаг 2. Для каждой из них записать логическое выражение, которое истинно только для этой строки.

Шаг 3. Сложить эти выражения и упростить результат.

распределительный

X

A B

A

B

A B

A) (

B)

B

A

A B (

A

A

A

исключения

распределительный

исключения

третьего

третьего

22

Синтез логических выражений (2 способ)

A	B	X
0	0	1
0	1	1
1	0	0	A B
1	1	1

Шаг 1. Отметить строки в таблице, где X = 0.

Шаг 2. Для каждой из них записать логическое выражение, которое истинно только для этой строки.

Шаг 3. Сложить эти выражения и упростить результат, который равен X .

Шаг 4. Сделать инверсию.

X A B X A B A B

? Когда удобнее применять 2-ой способ?

23

Синтез логических выражений

A	B	C	X
0	0	0	1	A B C
0	0	1	1	A B C
0	1	0	1	A B C
0	1	1	1	A B C
1	0	0	0
1	0	1	1	A B C
1	1	0	0
1	1	1	1	A B C

XA B C A B C

A B C A B C

A B C A B C

A B (C C)

A B (C C)

A C (B B)

A B A B A C

A (B B) A C

A A C

(A A) (A C) A C

24

Синтез логических выражений (2 способ)

A B C

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1 1 1 0 1 1 1

	X	X A B C A B C
	1	A C (B B)
	1	A C
	1	X A C A C
	1
	0	A B C
	1
	0	A B C
	1

25

Логические элементы компьютера

значок инверсии

A		A B	A	1	A B
		B	B
	НЕ	И		ИЛИ

	A	& A B	A	1	A B
	B		B
		И-НЕ		ИЛИ-НЕ

26

Логические элементы компьютера

Любое логическое выражение можно реализовать на элементах И-НЕ или ИЛИ-НЕ.

НЕ: A A A A A			И: A B A B
A	& A	A	& A B &	A B
		B

ИЛИ: A

A B A B

B

A

& A B

B

27

Составление схем

последняя операция — ИЛИ

X A B A B C

	A	A
		B
	B
		A
		B

C

И

&

A

1

X

A B C

& ACB &

28

Триггер (англ.

trigger – защёлка)

Триггер – это логическая схема, способная хранить 1

бит информации (1 или 0). Строится на 2-х элементах ИЛИ-НЕ или на 2-х элементах И-НЕ.

set, установка

S

1

1

R

reset, сброс

вспомогательный

выход

Q	S R Q			Q
	0	0	Q	Q
обратные связи	0	1	0	1
Q	1	0	1	0
основной	1	1	0	0
выход

режим

хранение

сброс

установка 1

запрещен

29

Полусумматор

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

A	Σ	S сумма			A	B	P	S
		P перенос			0	0	0	0
B
					0	1	0	1
P A B					1	0	0	1
S A B A B A B					1	1	1	0
A
			& A B
		B			1	S A B A B
		A	& A B
								Схема на 4-х
B			&	A B		P	? элементах?

30

Булева алгебра 2 разных упрощения?

спросил 1 год, 4 месяца назад

Изменено 1 год, 4 месяца назад

Просмотрено 2к раз

Хотите знать, почему следующее логическое выражение имеет 2 возможных упрощения? Являются ли эти два оба правильными? Большое спасибо !

Как это решает онлайн-учебник:

Как упростить

Как это решает онлайн-инструмент <--- То же, что и мой ответ

• логическая логика
• логическое выражение
• булева алгебра

3

Когда вы используете карту Карно, вы увидите, что они одинаковы. См. следующую карту Карно для этого логического выражения, почти полностью совпадающего с кругами:

Синий кружок соответствует выражению BC , красный кружок соответствует выражению B'C' . Оставшаяся ячейка по адресу AB'C по-прежнему нуждается в круге. Есть три способа создать круг, соответствующий этой ячейке:

В этом решении ячейке AB'C соответствует круг только с одной ячейкой. Однако это не самый большой круг, возможный на этой карте Карно. Круги, выбранные на карте Карно, выбираются как максимально возможный круг (в соответствии с правилами карты Карно).

«Настоящие» другие решения:

Зеленый кружок в этом решении соответствует AC . Осталось третье решение:

Зеленый кружок в этом решении соответствует AB' .

Это означает, что все эти три логических выражения равны:

• BC + B'C' + AB'C (можно еще упростить, показывает, что происходит, когда на картах Карно выбираются слишком маленькие круги)
• BC + B'C' + AC (ваше решение)
• BC + B'C' + AB' (решение из видео)

1

Зарегистрируйтесь или войдите в систему

Зарегистрируйтесь с помощью Google

Зарегистрироваться через Facebook

Зарегистрируйтесь, используя адрес электронной почты и пароль

Опубликовать как гость

Электронная почта

Обязательно, но не отображается

Опубликовать как гость

Электронная почта

Требуется, но не отображается

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

Я хочу упростить очень большую логическую функцию вида:

 f(a1,a2,. ...,an)= (a1+a2+a5).(a2+a7+a11+a23+a34) ......(а1+а3+ан).
 

‘.’ означает ИЛИ

‘+’ означает И

таких терминов может быть 100 (‘.’ друг с другом) значение n может доходить до 30.

Существует ли какой-либо реальный алгоритм для упрощения этого?

ВНИМАНИЕ: это не лабораторная работа, это небольшая часть моего проекта по генерации правил по грубому набору, где f — функция несходства.

• алгоритм
• математика
• время-сложность
• классификация
• логическое выражение

8

Известные способы сделать это:

• если количество переменных меньше 5, используйте алгоритм карты Карно
• , если количество переменных равно 5 или более, используйте алгоритм Куайна-МакКласки

Второй способ чаще всего используется на компьютере. Это таблично и прямолинейно. Первый способ лучше всего делать вручную и он более увлекательный, но вы не можете надежно использовать его для чего-либо более чем с 4 переменными.