Алгебра логики (стр. 4 )

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

Для образования сложных высказываний наиболее часто используются базовые логические операции, выражаемые с помощью логических связок «и», «или», «не».
Например,

Многие люди  не любят сырую погоду.

Пусть А = «Многие люди любят сырую погоду». Получаем логическую функцию F(A) = не А.

Связки "НЕ", "И", "ИЛИ" заменяются логическими операциями инверсия,конъюнкция, дизъюнкция. Это основные логические операции, при помощи которых можно записать любое логическое выражение.

Логическая формула (логическое выражение) - формула, содержащая лишь логические величины и знаки логических операций. Результатом вычисления логической формулы является ИСТИНА (1) или ЛОЖЬ (0).

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

       Основные (базовые) логические операции:

1. Логическое умножение (конъюнкция), от лат. konjunctio – связываю:
•  Объединение двух (или нескольких) высказываний в одно с помощью союза И;
•   в языках программирования - And. 
•  Принятые обозначения: /\ , •, и, and.
•  В алгебре множеств конъюнкции соответствует операция пересечения множеств. 

Конъюнкция истинна тогда и только тогда, все, входящие в нее высказывания истинны.

Пример: 
Рассмотрим составное высказывание  «2 • 2 = 4 и 3 • 3 = 10». Выделим простые высказывания:
А = «2 • 2 = 4» = 1 (т. к. это истинное высказывание)
В = «3 • 3 = 10» = 0 (т. к. это ложное высказывание)
Поэтому, логическая функция F(A, B) = A /\ B = 1 /\ 0 = 0 (в соответствии с таблицей истинности), то есть данное составное высказывание ложное.

2. Логическое сложение (дизъюнкция), от лат. disjunctio – различаю:
•  Объединение двух (или нескольких) высказываний в одно с помощью союза ИЛИ;
•   в языках программирования - Or. 
•  Обозначение:  \/, +, или, or.
•  В алгебре множеств дизъюнкции соответствует операция объединения множеств. 

Дизъюнкция ложна тогда и только тогда, все, входящие в нее высказывания ложны.

Пример: 
Рассмотрим составное высказывание  «2 • 2 = 4 или 2 • 2 = 5». Выделим простые выска-зывания:
А = «2 • 2 = 4» = 1 (т. к. это истинное высказывание)
В = «2 • 2 = 5» = 0 (т. к. это ложное высказывание)
Поэтому, логическая функция F(A, B) = A \/ B = 1 \/ 0 = 1 (в соответствии с таблицей истинности), то есть данное составное высказывание истинно.

3. Отрицание (инверсия), от лат. InVersion – переворачиваю:

•  Соответствует частице НЕ, словосочетаниям НЕВЕРНО, ЧТО или НЕ ЯВЛЯЕТСЯ ИСТИНОЙ, ЧТО;
•  в языках программирования - Not; 
•  Обозначение: не А, А, not
•  В алгебре множеств логическому отрицанию соответствует операция дополнения до универсального множества. 

  Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

 Пример:

А = {два умножить на два равно четырем} = 1.

 A= {Неверно, что два умножить на два равно четырем}= 0.

Рассмотрим высказывание А : "Луна — спутник Земли";  тогда  А будет формулироваться так:  "Луна — не спутник Земли".

Рассмотрим высказывание: «Неверно, что 4 делится на 3». Обозначим через А простое высказывание «4 делится на 3». Тогда логическая форма отрицания этого высказывания имеет вид А

Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке:
  1. инверсия;
  2. конъюнкция;
  3. дизъюнкция;
Для изменения указанного порядка выполнения логических операций используются круглые скобки.

Составные логические выражения алгебры высказываний называют формулами.
Истинно или ложно значение формулы можно определить законами алгебры логики, не обращаясь к смыслу: 
F = (0 \/ 1) /\ (0 \/ 1) = (0 \/ 1) /\ (1 \/ 0) =1 /\ 1=1 - истина
F = (0 /\ 1) \/ (1 \/ 1) = (1 /\ 0) \/ (0 \/ 0) = 0 \/ 0 = 0 - ложь

№1.

Определите значения следующих логических переменных:

1)  А = « Два умножить на два равно пяти»
2)  В =  «Всякий квадрат есть параллелограмм»
3)  С = «Всякий параллелограмм есть квадрат»

 Ответ: А =0, В = 1, С = 0

№2.

Определите значение истинности следующих высказываний:

1)  Высказывание "10 делится на 2 и 5 больше 3"
2)  Высказывание "10 делится на 2 и 5 не больше 3» 
3)  Высказывание "10 не делится на 2 и 5 больше 3" 
4)  Высказывание "10 не делится на 2 и 5 не больше 3" 

Ответ:
1)  истинное высказывание (1/\1=1)
2)  ложное  высказывание(1/\0=0)
3)  ложное  высказывание (0/\1=0)
4)  ложное  высказывание (0/\0=0)

№3.

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

1). Мне вас не жаль, года весны моей.
2). На холмах Грузии лежит ночная мгла;
  Шумит Арагва предо мною…
3). Унынья моего ничто не мучит, не тревожит.
4). Мне не спится, не огня;
  Всюду мрак и сон докучный.

 Ответ:
1)  F(A) = не А
2)  F(A, В) = А и В
3)  F(A, В) = не А и не В
4)  F(A, В, C, D) = не А и не В и С и D

№4.

Представьте  данное высказывание «Число 6 делится на 2, и число 6 делится на 3» в виде логической формулы.

Решение:  Обозначим через А простое высказывание «Число 6 делится на 2» - истинное высказывание, через В - «Число 6 делится на 3»- истинное высказывание. Простые высказывания соединены связкой  и (конъюнкция), очевидно логическая формула имеет вид  А /\ В. Ее значение  ((1/\1=1) - истина.

№5.

Даны два высказывания: А={3+2=5} и B={круг имеет форму прямоугольника}. Определите, чему равны составные высказывания:

1)  А /\ B 
2)    A \/ B 

 
Ответ:
1)  0
2)  1

 №6.

Определите истинность составного высказывания: (А /\B) /\ (C \/ D), состоящего из простых высказываний:

А = {Принтер – устройство вывода информации},
В = {Процессор – устройство хранения информации},
С = {Монитор – устройство вывода информации},
D = {Клавиатура – устройство обработки информации}.

 Решение:
Сначала устанавливаем истинность простых высказываний:  А = 1, В = 0, С = 1, D = 0.
Затем определим истинность составного высказывания, используя таблицы истинности логических операций:  (ø1/\ø0) /\ (1\/ 0) = (0 /\1) /\ (1 \/ 0) = 0
Ответ: (1/\0) /\ (1\/ 0) = (0 /\1) /\ (1\/ 0) = 0  - составное высказывание ложно.

№7.

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

«(2 * 2 = 4 /\ 3 * 3 = 10)  \/  (2 * 2 = 5 /\ 3 * 3 = 9)» .
 
Решение
Замените простые высказывания логическими переменными и установите их истинность или ложность:
А: «2*2 = 4» — истинно (1),
В: «3*3 = 10 — ложно (0),
С: «2*2 = 5» — ложно (0),
D: «3*3 = 9» — истинно (1).

Замените также логические связки «и» и «или» операциями логического умножения и логического сложения. Тогда составное высказывание примет вид следующего логического выражения: (А /\ В) \/ (С /\ D).

Подставьте вместо логических переменных их логические значения и определите истинность составного высказывания, используя таблицы истинности логических функций:
(1/\ 0) \/ (0/\1) = 0 + 0= 0.
 Ответ:  составное высказывание ложно.

 №1.

Из двух простых высказываний постройте сложное высказывание, используя логические связки «И», «ИЛИ»:

Например:

Все ученики изучают математику. Все ученики изучают литературу. -> Все ученики изучают математику и литературу.

1) Марина старше Светы. Оля старше Светы.

2) Синий клубок меньше красного. Синий клубок меньше зеленого.

3) Х=3, Х>2

4) В портфеле есть учебники. В портфеле есть тетради. В портфеле есть пенал.

5) Одна половина класса изучает английский. Вторая часть изучает немецкий язык.

6) Часть туристов любит чай. Остальная часть туристов любит молоко.

№2.

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

1)В книге более ста страниц;

2)Слово «стол» существительное;

3)Алеша моложе Тани;

4)В книге более ста страниц;