4.Формулы алгебры логики.

С помощью логических операций над высказывания­ми из заданной совокупности высказываний можно стро­ить различные сложные высказывания. При этом поря­док выполнения операций указывается скобками. Напри­мер, из трех высказываний х, у, z можно построить выс­казывания:

Первое из них есть дизъюнкция конъюнкции х и у и отрицания выказывания z, а второе высказывание есть импликация, посылкой которой является высказывание х,

а заключением - отрицание дизъюнкции высказывания у и конъюнкции высказываний х, z.

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

Формулы алгебры логики будем обозначать больши­ми буквами латинского алфавита А, В, С, ...

Для упрощения записи формул принят ряд соглаше­ний:

скобки можно опускать, придерживаясь следую­щего порядка действий:

- конъюнкция выполняется рань­ше, чем все остальные операции,

- дизъюнкция выполня­ется раньше, чем импликация и эквивалентность

- если над формулой стоит знак отрицания, то скобки тоже опускаются.

В связи с этим формулы:

могут быть записаны так:

Логическое значение формулы алгебры логики пол­ностью определяется логическими значениями входящих в нее элементарных высказываний. Например, логичес­ким значением формулы в случае, если х = 1, у = 1, z = 0 будет истина, то есть

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

Например, для формулы (указан порядок действий) таблица ис­тинности имеет вид:

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

Рассмотрим еще один пример на составление таблицы истинности:

. Таблица содержит 2³ = 8 строк:

Задачи для самостоятельного решения

1. Какие из следующих предложений являются высказываниями:

а)Москва - столица России;

б)

в) студент физико-математического факультета;

г) 5+3 – 6;

д) Луна есть спутник Марса;

е) а>0.

2. Приведите примеры предложений, а) являющихся высказываниями; б) не являющихся высказываниями.

3. Установите, истинно или ложно высказывание:

а )

б )

4. Среди следующих высказываний указать эле­ментарные (простые) и составные (сложные). В составных высказываниях выделить грамматические связки:

1) число 27 не делится на 3;

2) число 15 делится на 5 и на 3;

3) если число 126 делится на 9, то оно делится на 3;

4) число 7 является делителем числа 42;

5) число 1269 делится на 9 тогда и только тг когда 18 делится на 9.

5. Обозначьте элементарные высказывания буквами и запишите следующие высказывания с помощью символов алгебры логики:

1) 45 кратно 3 и 42 кратно 3;

2) 45 кратно 3 и 12 не кратно 3;

3) или

4) 2<5;

5) если число 212 делится на 3 и 4, то оно делится на 12;

6) число 212 - трехзначное и кратно 3 или 4.

6. Какие из следующих импликаций истинны:

1) если 2х2=4, то 2<3;

2) если 2х2=4, то 2>3;

3) если 2х2=5, то 2<3;

4) если 2х2=5, то 2>3?

7. Найдите логические значения х и у, при кото­рых выполняются равенства:

8. Известно, что импликация х  у истинна, а эк­вивалентность х  у ложна. Что можно сказать о зна­чении импликации у х ?

9. Известно, что эквивалентность х  у истинна. Что можно сказать о значении и ?

10. Известно, что х имеет значение 1. Что можно ска­зать о значениях импликации

11. Известно, что х  у имеет значение 1. Что можно сказать о значениях

12. Пусть х = 0, у = 1, z = 1 Определить логичес­кие значения нижеследующих сложных высказываний:

1 3. Составить таблицы истинности для формул:

7)

8)

Контрольные вопросы

1. Что называется высказыванием? Обозначения высказываний.

2. Определения простого (элементарного) и сложного (составного) высказываний.

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

4. Что называется отрицанием простого высказывания? Привести таблицу истинности.

5. Что называется дизъюнкцией двух простых высказываний? Привести таблицу истинности.

6. Что называется конъюнкцией двух простых высказываний? Привести таблицу истинности.

7. Что называется импликацией двух простых высказываний? Привести таблицу истинности.

8. Что называется эквиваленцией двух простых высказываний? Привести таблицу истинности.

9. Определение формулы алгебры логики.

10. В какой последовательности выполняются логические операции?