Глава II. Алгебра высказываний

Л.М.Мартынов. Вводный курс математики, стр.20-42

Вопросы для самопроверки

1. Являются ли высказываниями предложения:

a) «Семь больше пяти».

б) «Это легко, как дважды два».

в) «Ура!».

г) «Число 63 делится на любое простое число».

д) «Солдат-парикмахер бреет всех солдат своего подразделения, кто сам не бреется».

е) «Гнутся шведы!»

ж) «То, что здесь написано, ложь».

з) «Открой окно!»

2. Сформулируйте отрицания высказываний:

a) «Число 4 не является простым».

б) «Три больше пяти».

3. Сформулируйте импликацию высказывания «Число 12 делится на 3» и высказывания «Число 12 делится на 5».

4. Каково значение импликации при ложной посылке?

5. Если импликация ложна, то каковыP и Q?

6. Если значение дизъюнкции ложно, то каковоP ?

7. Если истинно, то каковы значениеP и ?

8. Если высказывания иP ложны, то каково Q?

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

a)

б)

в)

10. Какая операция в формуле выполняется первой, а какая последней?

11. Каков последний столбец формулы F в ее таблице истинности, если эта формула тождественно истинна?

12. Каково отрицание тождественно истинной формулы?

13. Является ли формула своим собственным логическим следствием?

14. Известны таблицы истинности для формул F и G от одних и тех же высказывательных переменных. Как проверить, что является тождественно истинной формулой.

15. Как связана равносильность формул F и G с их общей таблицей истинности?

16. Что можно сказать об истинности высказывания «Прямые a и b на плоскости параллельны или пересекаются»? Зависит ли его истинное значение от взаимного расположения прямых a и b? На каком законе логики основан ваш ответ?

Разберите решение следующих примеров

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

a) «11>0»;

б) «7 делится на 3»;

в) «3+4=7».

Решение. a) отрицанием истинного высказывания ”11>0» является ложное высказыванием«110».

б) отрицанием ложного высказывания «7 делится на 3» будет истинное высказывание«7 не делится на 3».

в) «3+47» ложное высказывание.

П р и м е р 2. Записать символически высказывание «15 делится на 3 и на 5».

Решение. Это высказывание есть конъюнкция двух высказываний «15 делится на 3» и«15 делится на 5». Поэтому получим:

П р и м е р 3. Прочитать по правилам русского языка символически записанное высказывание , если«2 – простое число»,«2 – четное число».

Ответ: « 2 – простое и четное число».

П р и м е р 4. Пусть «Иван умен»,«Петр умен»

Записать символически:

a) Иван умен и Петр глуп;

б) Иван и Петр оба глупы;

в) или Иван умен или Петр глуп;

г) если Иван умен, то Петр глуп.

Решение.

a)

б)

в)

г) .

П р и м е р 5. Пусть «У меня есть собака»,«У меня есть кошка”. Перевести на разговорный язык:

a) ;

б) ;

в) ;

г) .

Решение. a)У меня есть собака или у меня нет кошки;

б) Если у меня есть собака, то у меня нет кошки;

в) Или у меня нет собаки и есть кошка, или у меня нет кошки;

г) Если у меня нет собаки, то у меня нет кошки.

П р и м е р 6. Какие из данных высказываний истинны?

a) 35;

б) 77;

в) 30.

Решение. a) имеем дизъюнкцию: Так как первый член дизъюнкции истинный, то и вся дизъюнкция истинна.

б) высказывание «77» истинно, так как «7=7» истинно.

в) «30» ложно, т.к. оба члена дизъюнкции ложны.

П р и м е р 7. Постройте импликацию высказывания «25 при делении на 7 дает остаток 2» и «11>0» и определите ее истинностное значение.

Решение. «Если 25 при делении на 7 дает остаток 2, то 11>0» – истинное высказывание, поскольку истинно его заключение.

П р и м е р 8. Постройте эквиваленцию высказываний «25 при делении на 7 дает остаток 2» и «2 является конем уравнения », и определите ее истинное значение.

Решение. «25 при делении на 7 дает остаток 2 тогда и только тогда, когда 2 является конем уравнения ». Это высказывание истинно, как эквиваленция ложных высказываний.

П р и м е р 9.Какие из данных высказываний истинны:

a) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) .

Ответ: а), б), г), д), е) – истинны;

в), ж), з) – ложны.

П р и м е р 10. Построить таблицы истинности для следующих формул:

a) ;

б) ;

в) ;

г) .

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

Решение. Для сложной формулы F можно предложить следующий порядок заполнения таблицы истинности:

1.В строку выписываются сначала все атомы, а затем все подформулы F (не считая атомов), начиная с простых и кончая самой формулой F. Для каждой записи подготавливается столбец.

2.Атомам формулы F даются всевозможные наборы значений из множества {1;0}, компоненты которых записываются в соответствующие столбцы. Можно показать, что различных наборов значений истинности атомов (значит и строк таблицы) будет всего , гдеn – число атомов формулы F. Для удобства значения располагают так: под первым атомом подряд пишут половину (т.е. ) значений 1, затем столько же значений 0; под вторым атомом пишут подряд четвертую часть (т.е.) значений 1, затем столько же значений 0, повторяют это еще раз и т.д. Под последним атомом значений 1 и 0 чередуются.

3.Столбцы всех подформул формулы F и столбец самой формулы F заполняются согласно определениям соответствующих операций.

а) так как формула имеет две переменные, ее таблица истинности содержит четыре строки .

1	1	1	0	1	1
1	0	0	0	0	1
0	1	0	1	1	1
0	0	0	1	1	1

Так как последний столбец таблицы содержит только значения 1, то формула является тавтологией.

Заметим, что 3, 4, 5 столбцы являются вспомогательными и в таблице истинности могут отсутствовать.

б) Поскольку формула содержит три высказывательные переменные, то ее таблица истинности содержит восемь строк .

1	1	1	1	0	0	0	0	0
1	1	0	1	0	0	1	0	0
1	0	1	1	0	0	0	0	0
1	0	0	1	0	0	1	0	0
0	1	1	1	1	1	0	0	0
0	1	0	0	1	1	1	1	0
0	0	1	1	1	0	0	0	0
0	0	0	0	1	0	1	0	1

Эта формула является одновременно выполнимой и опровержимой, так как на наборе значений переменных 0, 0, 0 формула принимает значение 1, а на остальных наборах формула принимает значение 0.

в)

1	1	0
1	0	0
0	1	0
0	0	0

В этой таблице не приведен вспомогательный столбец. Формула является противоречием.

г)

1	1	1				1
1	1	0				1
1	0	1				1
1	0	0				0
0	1	1				1
0	1	0				1
0	0	1				1
0	0	0				1

В построенной таблице не заполнены вспомогательные столбцы (сделайте это самостоятельно). Формула является одновременно выполнимой и опровержимой.

П р и м е р 11. Проверить являются ли следующие формулы равносильными:

a) и;

б) и.

Решение.

а) составим таблицы истинности для данных формул (их удобно совместить). Получим:

1	1	0	1	1	1
1	0	0	0	0	0
0	1	1	1	0	0
0	0	1	1	0	0

Сравнивая два последних столбца, мы видим, что они одинаковые. Значит, формулы равносильны (или логически равны): .

б) составим таблицы истинности:

1	1	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	0	1	0	0	1	0	0
1	0	0	0	0	0	0	0
0	1	1	1	1	1	1	1
0	1	0	1	1	1	1	1
0	0	1	1	1	1	1	1
0	0	0	1	1	1	1	1

Сравнивая 6-й и 8-й столбцы таблицы, видим, истинностные значения формул различаются при значениях переменных ,,. Следовательно, эти формулы не являются равносильными.

П р и м е р 12. Упросить формулы, применяя основные равносильности алгебры высказываний (стр. 32 учебного пособия Л.М.Мартынова).

а) ;

б);

в);

г).

Решение.

а) (здесь применили дистрибутивный закон, закон противоречия 7^’ и свойство 0 – 8^’).

б) , т.к. если обозначитьчерезХ, то получим по закону поглощения 4.

в).

г)

.

П р и м е р 13. Записать формулу с помощью только конъюнкции и отрицания.

Решение.

.

П р и м е р 14. Доказать, что формула есть логическое следствие формул.

Решение. 1-й способ. Докажем, что по определению. Для этого составим всевозможные наборы истинностных значений для высказывательных переменных, вычислим для них соответствующие значения посылкии значенияи сравним только те значения этих формул, при которых посылка истинна.

Легко понять, что первая формула принимает значение 1 лишь для набора истинностных значений 0,0. Требуемое логическое следование вытекает из фрагмента таблицы истинности

0	0	1	1

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

Докажем это с помощью преобразований:

3-й способ. Методом от противного. Предположим, что формула не является логическим следствием формули. Значит, при истинных посылкахиформулапринимает значение 0. Т.к., то,. Но тогда мы получаем противоречие с предположением об истинности посылки. Полученное противоречие доказывает, что наше предположение неверно, и значит, формулаявляется логическим следствием посылоки.