Конспект_ОСНОВЫ ЛОГИКИ(3)(2). Решение логических задач. Учитель информатики Батракова Л. В

• Название: Решение логических задач. Учитель информатики Батракова Л. В
• Дата: 18.01.2019
• Размер: 1.45 Mb.
• Имя файла: Конспект_ОСНОВЫ ЛОГИКИ(3)(2).pdf
• Тип: Решение; #64191
• страница: 1 из 7

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
1
Логика (от древнегреческого – «наука о рассуждении»)– это наука, изучающая методы
установления истинности или ложности одних высказываний на основе истинности или ложности
других высказываний.
Древнегреческий философ Аристотель стал основоположником формальной логики, которая изучает высказывания.
Высказывание (суждение) – некоторое предложение, которое может быть истинно (верно) или
ложно.
(Например, «Сейчас идет дождь.» и «Вчера жирафы улетели на север.» - это высказывания, а «Который час?» высказыванием не является.)
В классической формальной логике высказывание может быть истинно или ложно. Если обозначить истинное значение единицей, а ложное – нулем, то получится, что формальная логика представляет собой правила выполнения операций с нулями и единицами, т.е. с двоичными кодами. Английский ученый
Джордж Буль предложил применять для исследования логических высказываний математические методы.
Позже этот раздел математики получил название алгебра логики или булева алгебра.
Алгебра логики – это математический аппарат, с помощью которого записывают, вычисляют,
упрощают и преобразовывают логические высказывания.
Алгебра логики определяет правила выполнения операций с логическими величинами, которые могут быть равны только 0 или 1.
Утверждение
– суждение, которое требуется доказать или опровергнуть.
Логическое выражение – запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины. В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая 1) или ЛОЖЬ (логический 0).
Сложное логическое выражение – логическое выражение, составленное из одного или нескольких простых (или сложных) логических выражений, связанных с помощью логических операций.
Таблица истинности – задает логическую функцию, то есть правила преобразования входных
логических значений в выходные.
Таблица истинности состоит из двух частей: слева перечисляются все возможные значения исходного высказывания, а в последнем столбце записывают результат выполнения логической операциидля каждого из этих вариантов.

Основные логические операции
1.
Логическое отрицание
(инверсия, логическое НЕ) -
если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным. Обозначение:

A или A .
Таблица истинности:
2.
Логическое сложение (дизъюнкция, логическое ИЛИ) - это новое сложное выражение будет истинным тогда и только тогда, когда истинно хотя бы одно из исходных (простых) выражений.
Обозначение: A

B или A+B
A

А
0 1
1 0

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
2
Таблица истинности:
3.
Логическое умножение (конъюнкция, логическое И) - это новое сложное выражение будет истинным только тогда, когда истинны оба исходных простых выражения. Обозначение: A

B
или A ·
B или A
.
Таблица истинности:
4.
Логическое следование (импликация) - связывает два простых логических выражения, из которых первое является условием (А), а второе (В)– следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначение: A

B.
Таблица истинности:
5.
Логическая равнозначность (эквивалентность, тождество) - определяет результат сравнения двух простых логических выражений А и В. Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначение: A
≡ B или A

B.
Таблица истинности:
6.
Сложение по модулю 2 (исключающее ИЛИ, в просторечье XOR) - определяет результат сравнения двух простых логических выражений А и В. Результатом является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения различны.
Обозначение: A

B.
A
B
А

В
1 1
1 1
0 1
0 1
1 0
0 0
A
B
А

В
1 1
1 1
0 0
0 1
0 0
0 0
A
B
А

В
1 1
1 1
0 0
0 1
1 0
0 1
A
B
A
≡
B
1 1
1 1
0 0
0 1
0 0
0 1

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
3
Таблица истинности:
7.
Штрих Шеффера (‘И-НЕ’, англ. nand=’not and’) – определяет результат, обратный операции конъюнкции. A | B =

(A • B). Обозначается: A | B.
Таблица истинности:
8.
Стрелка Пирса (‘ИЛИ-НЕ’, англ. nor=’not or’) - определяет результат, обратный операции дизъюнкции. A

B =

(A + B). Обозначается: A

B.
Таблица истинности:

Операции
инверсия (

), конъюнкция (•) и дизъюнкция (+) – являются базовыми, через них можно выразить другие операции.

Приоритет логических операций в сложном логическом выражении
1. инверсия
2. конъюнкция
3. дизъюнкция
4. импликация
5. эквивалентность
6. сложение по модулю 2
Для изменения указанного порядка выполнения операций используются скобки.

Построение таблицы истинности для сложных выражений
Таблица истинности - это таблица, устанавливающая соответствие между всеми возможными наборами логических переменных, входящих в логическую функцию и значениями функции.
Таблицы истинности применяются для:
- вычисления истинности сложных высказываний;
- установления эквивалентности высказываний.
A
B
A

B
1 1
0 1
0 1
0 1
1 0
0 0
A
B
A
|
B
0 0
1 0
1 1
1 0
1 1
1 0
A
B
A

B
0 0
1 0
1 0
1 0
0 1
1 0

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
4
Для построения таблицы истинности надо определить количество строк и столбцов.
Количество строк = 2
n
+ одна строка для заголовка (n - количество простых высказываний).
Количество столбцов = количество переменных + количество логических операций.
При построении таблицы надо учитывать все возможные сочетания логических значений 0 и 1 исходных выражений. Затем – определить порядок действий и составить таблицу с учетом таблиц истинности основных логических операций.
ПРИМЕР: составить таблицу истинности сложного логического выражения D =

A

( B

C )
А,В, С - три простых высказывания, поэтому :
количество строк = 2 3
+1 = 9 (n=3, т.к. на входе три элемента А, В, С)
количество столбцов:
1) А
2) В
3) С
4)

A это инверсия А (обозначим Е)
5) B

C это операция дизъюнкции (обозначим F)
6) D =

A

( B

C ), т.е. D = E

F это операция конъюнкции
А
В
С
E =

А
F = В

С
D = E

F
1
1
1
0 1
0
1
1
0
0 1
0
1
o
1
0 1
0
1
o
0
0 0
0
0
1
1
1 1
1
0
1
0
1 1
1
0
0
1
1 1
1
0
0
0
1 0
0

Основные законы алгебры логики
1.
Закон рефлексивности (переместительный закон с самой собой)
А ∨ А = А
A ∧ A = A
2.
Закон коммутативности (переместительный закон)
A ∨ B = B ∨ A
A ∧ B = B ∧ A
3.
Закон ассоциативности (сочетательный закон)
(A ∧ B) ∧ C = A ∧ (B ∧ C)
(A ∨ B) ∨ C = A ∨ (B ∨ C)
4.
Закон дистрибутивности (распределительный закон)
A ∧ (B ∨ C) = A ∧ B ∨ A ∧ C
A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C)
5.
Закон отрицания отрицания
¬ (¬ A) = A
6.
Законы де Моргана
¬ (A ∧ B) = ¬ A ∨ ¬ B
¬ (A ∨ B) = ¬ A ∧ ¬ B

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
5
7.
Законы поглощения
A ∨( A ∧ B) = A
A ∧ (A ∨ B) = A
A ∨ (¬ A ∧ B)=A ∨ B
8.
Закон непротиворечия
A ∧¬ A = 0
9.
Закон исключенного третьего
A ∨ ¬ A = 1
10.
Законы нуля и единицы
A ∧ 0 = 0
A ∧ 1 = A
A ∨ 0 = A
A ∨ 1 = 1

Выражение дополнительных логических операций через базовые операции
1.
Импликация:
А

В =
¬ A ∨ B
2.
Эквиваленция:
A ≡ B =
(A ∧ B) ∨ (¬ A ∧ ¬ B)
3.
Исключаюшщее ИЛИ:
A

B =
(¬ A ∧ B) ∨ ( A ∧ ¬ B)

Типовые задачи ЕГЭ, для решения которых требуются знания алгебры логики
Часть 1. Логические выражения
1. Определение равносильности выражений. Решение этих задач основано на непосредственном применении законов алгебры логики.
Пример 1:
Какое логическое выражение эквивалентно выражению ¬A

B

¬(A

¬B)?
1) ¬B

¬A
2) A

¬B
3) B

¬A
4) B

A
Решение: Фактически это задание на применение законов де Моргана:
¬ (A

B) = ¬ A

¬ B
¬ (A

B) = ¬ A

¬ B
И закона повторения: A

A=A
Применив этот закон к выражению: ¬A

B

¬(A

¬B), получим (¬A

B )

(¬A

B)= ¬A

B.
Ответ: 3
2.
Построение и анализ таблиц истинности логических выражений.
Для решения этих задач достаточно проверять предлагаемые ответы один за другим, поочередно подставляя в соответствующее логическое выражение значения переменных из каждой строки таблицы и проверяя, получается ли в результате указанное в этой же строке таблицы требуемое значение F. При этом, если для какой-то из строк таблицы получается неправильный результат, то можно прервать проверку данного варианта ответа и сразу перейти к следующему варианту.
Пример 1:
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
X
Y
Z
F
0 1
1 0
1 1
1 1
0 0
1 1
Какое выражение соответствует F?
1) X /\ ¬Y /\ ¬Z 2) ¬X /\ ¬Y /\ Z 3) ¬X \/ ¬Y \/ Z 4) X \/ ¬Y \/ ¬Z

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
6
Решение: Надо помнить, что:

логическая сумма X \/ Y \/ Z равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно);

логическое произведение X /\ Y /\Z равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно).
Проверим все выражения на соответствие таблице истинности:
X
Y
Z
F
X /\ ¬Y /\ ¬Z
¬X /\ ¬Y /\ Z¬X \/ ¬Y \/ ZX \/ ¬Y \/ ¬Z
0 1
1 0
0 0
1 0
1 1
1 1
0 0
1 1
0 0
1 1
0 1
1 1
Из таблицы видно, что указанному условию удовлетворяет только выражение: X \/ ¬Y \/ ¬Z
Ответ: 4
Пример 2:
Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F? x
1 x
2 x
3 x
4 x
5 x
6 x
7
F
0
1
0
1
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
1
0
1) (x1

x2)

¬x3

x4

¬x5

x6

¬x7
2) (x1

x2)

¬x3

x4

¬x5

x6

x7
3) (x1

¬x2)

x3

¬x4

¬x5

x6

¬x7
4) (¬x1

¬x2)

x3

¬x4

x5

¬x6

x7
Решение: В последнем столбце таблицы всего одна единица, поэтому стоит попробовать использовать функцию, состоящую из цепочки операций «И», это ответы 1, 3 или 4.
Для этой «единичной» строчки получаем, что инверсия (операция «НЕ») должна быть применена к переменным x
3, x
5 и x
7
, которые равны нулю:
x
1
x
2
x
3
x
4
x
5
x
6
x
7
F
1
1
0
1
0
1
0
1
Таким образом, остается только вариант ответа 1, т.к. в ответах 3 и 4 переменная x
3
указана без инверсии.
Проверяем скобку (x1

x2). В данном случае она равна 1, что соответствует условию.
Ответ: 1
Пример 3:
Дано логическое выражение, зависящее от 5 логических переменных:
X
1

¬X
2

X
3

¬X
4

X
5
Сколько существует различных наборов значений переменных, при которых выражение ложно?
1) 1 2) 2 3) 31 4) 32
Решение: Перепишем выражение в других обозначениях:
5 4
3 2
1
X
X
X
X
X




Таблица истинности для выражения с пятью переменными содержит 2 5
= 32 строки (различные комбинации значений этих переменных). Логическое произведение истинно в том и только в том случае, когда все сомножители равны 1, поэтому только один из этих вариантов даст истинное значение выражения, а остальные 32 – 1 = 31 вариант дают ложное значение.
Ответ: 3
Пример 4:
Логическая функция F задаётся выражением (x

¬y

¬z)

(¬x

y). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z?
?
?
?
F
0
0
0
1
0
0
1
0
0
1
0
1

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
7
0
1
1
1
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая 1-му столбцу; затем – буква, соответствующая 2-му столбцу; затем – буква, соответствующая 3-му столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение:
Запишем заданное выражение в более простых обозначениях:
)
(
)
(
y
x
z
y
x
F






Используя известные тождества алгебры логики:
a
a


0
,
0


a
a
и распределительный закон для операции «И»
)
(
)
(
c
a
b
a
c
b
a






преобразуем исходное выражение:
)
(
)
(
)
(
)
(
)
(
)
(
)
(
z
y
x
z
y
x
z
y
x
z
z
y
x
z
y
x
y
x
z
y
x
F

























Каждая дизъюнкция в выражении соответствует строке таблицы истинности, в которой F=0.