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

Логические переменные

Логика – наука о «высказываниях».
Высказывание– это форма мышления, в которой

Булева алгебра

Двоичное кодирование – все виды информации кодируются с помощью 0

Логические высказывания

Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно

Обозначение высказываний

A – Сейчас идет дождь.
B – Температура выше нуля.

простые высказывания

Логические функции

Логическая функция (операция) – функция F(x1, x2,…xn), значение которой и

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

Перечисление значений функции F(x1, x2,…xn) для всех вариантов задания аргументов

Логические элементы

Описание преобразования двоичных сигналов в электрических схемах компьютера производится с

ЭЛЕМЕНТАРНЫЕ ЛОГИЧЕСКИЕ ФУНКЦИИ (ОПЕРАЦИИ)

Логическое отрицание (инверсия)

Обозначение: X, ¬X, not X.
Пример:
X – Идет снег
X -

Элемент «НЕ»

Элемент НЕ (инвертор) – реализует операцию отрицания (выдает на выходе

Логическое умножение (конъюнкция)

Обозначения: &, Λ, •, and
Пример:
X1 – Идет снег.
X2 –

Элемент И (конъюнктор) – реализует конъюнкцию двух или более входных сигналов.

Логическое сложение (дизъюнкция)

Обозначения: ∨, +, or
Пример:
X1 – Идет снег.
X2 – Идет

Элемент «ИЛИ»

Элемент ИЛИ (дизъюнктор) – реализует дизъюнкцию двух или более входных

Строгая дизъюнкция

Обозначения:
⊕, XOR
Пример:
X1 – Первый урок физика.
X2 – Первый

Следование (импликация)

Обозначения: →
Пример:
X1 – Идет дождь.
X2 – Асфальт мокрый.
X1→X2 Если идет

Равнозначность (эквиваленция)

Обозначения:
↔ ⇔ = ≡
Пример:
X1 – Небо голубое.
X2 –Светит

Отрицание логического умножения
Обозначения: |

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

И-не (Штрих Шеффера)

Отрицание логического сложения
Обозначения: ↓

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

ИЛИ-не (Стрелка Пирса)

Приоритет логических операций

Инверсия
Конъюнкция
Дизъюнкция и строгая дизъюнкция
Импликация и эквиваленция

¬
^
∨
⊕
→
⇔

ЗАКОНЫ ЛОГИКИ

Переместительный (коммутативный)закон

X·Y = Y·X
X∨Y = Y∨X

Сочетательный (ассоциативный)закон

(X·Y)·Z = Y·(X·Z)
(X∨Y)∨Z = Y∨(X∨Z)

Распределительный (дистрибутивный)закон

X·(Y∨Z) = X·Y∨X·Z
X∨Y·Z = (X∨Y)·(X∨Z)

Закон отрицания (де Моргана)

X·Y

Основные тождества

X·1 = Х
X∨1 = 1
X·0 = 0
X∨0 = Х

Правила исключения

Основные тождества

X·Х = Х
X∨Х = Х
X·Х = 0
X∨Х = 1
X =

Правила упрощения выражений

Правило
поглощения

X∨Х·Y = Х

X∨Х·Y=X·1∨Х·Y=X·(1∨Y)=X·1=X

Правило
свертки

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

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

Порядок вычислений:
скобки
НЕ
И
ИЛИ, исключающее ИЛИ
импликация
эквивалентность

A

B

V

∙

V

B

C

∙

A

С

∙

1 4 2 5 3

Вычислите значение функции

При x1=0, x2=0, x3=1
При x1=1, x2=1, x3=1

1

0

Вычислите значение функции

При x1=1, x2=0, x3=0
При x1=0, x2=1, x3=0

1

0

Вычислите значение функции

При x1=1, x2=0, x3=0
При x1=0, x2=1, x3=0

1

1

Определите значение логического выражения

При X =1

1

1

При X =2

При X =3

При X

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

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

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

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

X1

X2

X3

Y

При x1=0, x2=1, x3=1
При x1=1, x2=0, x3=1

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

X1

X2

Y

0

1

1

0

Запишите логическую функцию, соответсвующую логической схеме

X1

X2

X3

Y

Запишите логическую функцию, соответсвующую логической схеме

X1

X2

X3

Y

ЕГЭ 2012 - А3

Дан фрагмент таблицы истинности выражения F:

Какое выражение

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

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

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

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

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

Упрощение выражений

1

2

3

Упрощение выражений

1

2

3

4

ЕГЭ-2012 А10 Знание основных понятий и законов математической логики

1

2

3

4

Укажите, какое логическое

Задачи (упрощение)

Какое логическое выражение равносильно выражению A ∧ ¬(¬B ∨ C)?

Запишите логическую функцию, соответствующую логической схеме и упростите

X1

X2

Y

X3

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

Y=F(x1, x2,…xn)

Совершенная дизъюнктивная нормальная форма

СДНФ – форма, в которой функция представлена в

СДНФ функции

F(x1,x2, x3)=1 на 1, 2, 5, 6 наборах таблицы истинности
Записать

СДНФ функции

F(x1,x2, x3)=1 на 1, 2, 5, 6 наборах таблицы истинности
Записать

СДНФ функции

F(x1,x2, x3)=1 на 1, 3, 6, 7 наборах таблицы истинности
Записать

СДНФ функции

F(x1,x2, x3)=1 на 3, 5, 6, 7 наборах таблицы истинности
Записать

СДНФ функции

F(x1,x2, x3)=1 на 1, 3, 5, 6, 7 наборах таблицы

СДНФ функции ДЗ

1) F(x1,x2, x3)=1 на 0, 2, 6, 7 наборах

СДНФ функции A→B

СДНФ функции A⇔B

СДНФ функции A⊕B

ЕГЭ-2012 А10 Знание основных понятий и законов математической логики

1

2

3

4

Для какого имени

ЕГЭ-2012 А10 Знание основных понятий и законов математической логики

1

2

3

4

(2012-демо) Какое из

Логические уравнения
Каково наибольшее целое число X, при котором истинно высказывание
(90

Логические уравнения
3. Укажите значения логических переменных K, L, M, N, при

Логические уравнения
Сколько различных решений имеет уравнение 
(¬K ∨¬ L ∨ ¬ M)

Логические уравнения

Найти все решения уравнения
((B \/ C)⋅ A)→(A ⋅ C

Логические уравнения

Найти все решения уравнения
A \/ B \/ (B→(C \/

Использование алгебры логики
Следующие два высказывания истинны:
1. Неверно, что если корабль A

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

Использование алгебры логики
Четверо друзей Андрей, Борис, Сергей и Дмитрий решили пойти

Логические задачи

Три свидетеля дали показания о том, что преступники скрылись с

Логические задачи

- черном Ауди (1-ый свидетель),
- на синем Форде (2-ой свидетель),
на

Логические задачи

- черном Ауди (1-ый свидетель),
- на синем Форде (2-ой свидетель),
на

Логические задачи

Алеша, Боря и Володя нашли в море сосуд.
Алеша сказал:

Логические задачи

Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу

Логические задачи

Д, Даша и Маша остались дома одни. Кто-то из них

Логические задачи

А) Петя: "Я не ел. Маша тоже не ела"; Б) Вася:

Логические задачи

Девять школьников, остававшихся в классе на перемене, были вызваны к

Логические задачи

(На одной улице стоят в ряд 4 дома, в которых

Логические задачи

Аня, Вика и Сергей решили пойти в кино.
Учитель хорошо

Диаграммы Вена (круги Эйлера)

A·B

A+B

A⊕B

A→B

A↔B

Диаграмма МХН (Е.М. Федосеев)

Хочу

Могу

Надо

1

2

3

4

5

6

7

8

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

Задачи

NA|B = NA+ NB

A

B

A

B

NA|B = NA+ NB – NA&B

огурцы | помидоры

50

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

Задачи

Динамо

Спартак

Рубин

1

2

3

Динамо & Рубин
= 1 + 2 = 320

Спартак &

Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в

Задачи

А (сканер)

B (принтер)

NA|B = NA+ NB – NA&B

принтер | сканер

450

сканер

принтер

200

250

0

сканер

принтер

монитор

90

40

Сложная задача

Ниже приведены запросы и количество страниц, которые нашел поисковый сервер

§ 23. Предикаты и кванторы

Предикаты

Предикат (логическая функция) – это утверждение, содержащее переменные.
Предикат-свойство – от одной

Предикаты и кванторы

Предикаты задают множества:

Предикаты, которые всегда истинны:

для всех вещественных чисел

«Для

Кванторы

Какой квантор использовать?
« … моря соленые».
« … кошки серые».
« … числа

Кванторы

Дано:
A = «Все люди смертны» = 1.
B = «Сократ – человек»

Несколько кванторов

– предикат от переменной y

Квантор связывает одну переменную:

– предикат

Отрицание

НЕ «для любого x выполняется P(x)» ⇔
«существует x, при котором не

X1

X2

X3

Y

ЕГЭ -2016 -2

Задана лог. функция F = (¬z)∧x ∨ x∧y.
Определите,

ЕГЭ -2015 -2

Александра заполняла таблицу истинности для выражения F. Она успела