Доказать равносильность формул: 1) составлением таблиц истинности; 2) приведением формул к СДНФ или СКНФ с помощью равносильных преобразований.
1. а); б).
2. а); б).
3. а); б).
4. а); б).
5. а); б).
6. а); б).
7. а); б).
8. а); б).
9. а); б).
10. а); б).
11. а); б).
12. а); б).
13. а); б).
14. а); б).
15. а); б).
16. а); б).
17. а); б).
18. а); б).
19. а); б).
20. а); б).
21. а); б).
22. а); б).
23. а); б).
24. а); б).
25. а); б).
Пример. Доказать равносильность формул
с помощью: 1) таблиц истинности; 2) равносильных преобразований.
Решение: Первый способ. Строим таблицы истинности для формул F и G:
P
Q
R
(1)
(2)
(3)
F
G
(1)&(2)&(3)
I
Из построенных таблиц для F и G видно, что их значения для конкретных высказываний совпадают.
Второй способ. Приведём формулу F равносильными преобразованиями к формуле G.
Преобразование (1) осуществляется с использованием равносильности . Преобразование (2) осуществляется с использованием дистрибутивности операции & относительно Ú к двум первым скобкам.
Преобразование (3) осуществляется с использованием следующих равносильностей:
а) ; б) ;
в) ; г) .
Преобразование (4) осуществляется с использованием дистрибутивности операции & относительно Ú. Преобразование (5) осуществляется с использованием равносильностей в), г), использованных при преобразовании (3).
Задача 5
Проверить правильность умозаключений методом от противного:
1. а) Если противоположные стороны четырехугольника попарно параллельны, то он является параллелограммом. Если четырехугольник – ромб, то его противоположные стороны попарно параллельны. Следовательно, если четырехугольник – ромб, то он – параллелограмм.
б) Матрица обладает обратной тогда и только тогда, когда она является невырожденной и ее определитель отличен от нуля. Матрица является невырожденной тогда и только тогда, когда ее определитель отличен от нуля. Следовательно, матрица обладает обратной тогда и только тогда, когда она является невырожденной.
2. а) Четырехугольник является параллелограммом тогда и только тогда, когда его противоположные стороны попарно равны и параллельны. Если противоположные стороны четырехугольника попарно параллельны, то они равны. Следовательно, четырехугольник является параллелограммом тогда и только тогда, когда его противоположные стороны попарно параллельны.
б) Если система векторов содержит нулевой вектор или два одинаковых вектора, то она является линейно зависимой. Данная система векторов линейно независима. Следовательно, система не содержит ни нулевого вектора, ни одинаковых векторов.
3. а) Если формула является выполнимой, то она является тавтологией или не является противоречием. Если формула – тавтология, то она не является противоречием. Следовательно, если формула – выполнимая, то она не является противоречием.
б) Если матрица А – невырожденная, то ее определитель отличен от нуля, а ее строки образуют линейно независимую систему векторов. Если определитель отличен от нуля, то матрица А – невырожденная и ее строки образуют линейно независимую систему векторов. Следовательно, матрица А – невырожденная тогда и только тогда, когда ее определитель отличен от нуля.
4. а) Если число векторов совпадает с рангом системы, то система векторов линейно независима и является базисом. Если система векторов линейно независима или является базисом, то число векторов в системе совпадает с ее рангом. Следовательно, система векторов является базисом тогда и только тогда, когда число векторов в ней совпадает с рангом системы.
б) Если я приду в институт и получу стипендию, то я пойду на занятия. Если я приду в институт и не пойду на занятия, то я все равно получу стипендию. Следовательно, я пойду на занятия или не приду в институт.
5. а) Если последовательность монотонная и ограниченная, то она имеет предел. Если последовательность монотонная и имеет предел, то она ограничена. Данная последовательность монотонная. Следовательно, монотонная последовательность имеет предел тогда и только тогда, когда она ограничена.
б) Параллелограмм является прямоугольником тогда и только тогда, когда его диагонали или все его углы равны. Диагонали параллелограмма равны тогда и только тогда, когда все его углы равны между собой. Следовательно, параллелограмм является прямоугольником тогда и только тогда, когда его диагонали равны.
6. а) Если данный параллелограмм имеет равные диагонали, то он является прямоугольником или квадратом. Данный параллелограмм не является квадратом. Следовательно, если данный параллелограмм имеет равные диагонали, то он является прямоугольником.
б) Число делится на 3 тогда и только тогда, когда сумма его цифр в десятичной записи делится на 3 или на 9. Число делится на 3 тогда и только тогда, когда сумма его цифр в десятичной записи делится на 3. Следовательно, если сумма цифр в десятичной записи делится на 9, то число делится на 3.
7. а) Матрица обладает обратной тогда и только тогда, когда она является невырожденной и ее определитель отличен от нуля. Матрица является невырожденной тогда и только тогда, когда ее определитель отличен от нуля. Следовательно, матрица обладает обратной тогда и только тогда, когда ее определитель отличен от нуля.
б) Если четырехугольник – параллелограмм, то его противоположные стороны попарно параллельны. Если четырехугольник – ромб, то две его противоположные стороны попарно параллельны. Следовательно, если четырехугольник – ромб, то он – параллелограмм.
8. а) Треугольник является равнобедренным тогда и только тогда, когда его боковые стороны и углы при основании равны. Треугольник является равнобедренным тогда и только тогда, когда его боковые стороны равны. Следовательно, если боковые стороны треугольника равны, то равны и углы при основании.
б) Четырехугольник является квадратом или ромбом тогда и только тогда, когда все его стороны равны. Если четырехугольник – квадрат, то он является и ромбом. Следовательно, четырехугольник является ромбом тогда и только тогда, когда все его стороны равны.
9. а) Если матрица А – невырожденная, то ее определитель отличен от нуля, а ее строки образуют линейно независимую систему векторов. Если определитель отличен от нуля, то матрица А – невырожденная и ее строки образуют линейно независимую систему векторов. Следовательно, если матрица А – невырожденная и ее определитель отличен от нуля, то строки этой матрицы образуют линейно независимую систему векторов.
б) Четырехугольник является параллелограммом тогда и только тогда, когда его противоположные стороны равны и параллельны. Данный четырехугольник имеет равные противоположные стороны. Следовательно, данный четырехугольник будет параллелограммом тогда и только тогда, когда его противоположные стороны параллельны.
10. а) Целое число делится на 6 тогда и только тогда, когда оно делится на 2 и на 3. Данное число не делится на 6. Следовательно, если данное число делится на 2, то оно не делится на 3.
б) Если число векторов совпадает с рангом системы, то система векторов линейно независима и является базисом. Если система векторов линейно независима или является базисом, то число векторов в системе совпадает с ее рангом. Следовательно, система векторов является базисом тогда и только тогда, когда она линейно независима.
11. а) Параллелограмм является прямоугольником тогда и только тогда, когда его диагонали или все его углы равны. Диагонали параллелограмма равны тогда и только тогда, когда все его углы равны между собой. Следовательно, параллелограмм является прямоугольником тогда и только тогда, когда все его углы равны.
б) Если функция дифференцируемая и ее производная положительна, то функция монотонно возрастающая. Если функция дифференцируемая и монотонно возрастающая, то производная функции положительна. Следовательно, если функция дифференцируемая, то она является монотонно возрастающей тогда и только тогда, когда ее производная положительна.
12. а) Если волки будут сыты, а овцы целы, то пастухи будут довольны. Если волки не будут сыты, то пастухи будут довольны тогда и только тогда, когда овцы целы. Следовательно, если пастухи довольны, то волки сыты или овцы целы.
б) Число является четным тогда и только тогда, когда оно делится на 2 или на 4. Число является четным тогда и только тогда, когда оно делится на 2. Следовательно, если число делится на 4, то оно четное и делится на 2.
13. а) Неверно, что если Анри украл машину, то Луи и Том видели это. Луи видел, как Анри украл машину. Следовательно, Анри украл машину, но Том не видел этого.
б) Число делится на 5 тогда и только тогда, когда оно оканчивается нулем или цифрой 5. Данное число не оканчивается цифрой 5. Следовательно, данное число делится на 5 тогда и только тогда, когда оно оканчивается нулем.
14. а) Если целое число делится на 2 и на 3, то оно делится на 6. Если целое число делится на 2 и не делится на 3, то оно не делится на 6. Следовательно, если целое число делится на 2, то оно делится на 6 тогда и только тогда, когда оно делится на 3.
б) Треугольник является равнобедренным тогда и только тогда, когда его боковые стороны и углы при основании равны. Если боковые стороны треугольника равны, то равны и углы при основании. Следовательно, треугольник является равнобедренным тогда и только тогда, когда его боковые стороны равны.
15. а) Подсистема векторов является базисом исходной системы тогда и только тогда, когда она линейно независима и любой вектор исходной системы линейно выражается через векторы этой подсистемы. Данная подсистема векторов является линейно независимой. Следовательно, данная подсистема векторов является базисом исходной системы тогда и только тогда, когда любой вектор исходной системы линейно выражается через векторы этой подсистемы.
б) Если сторож выходил на работу и у преступника был ключ, то ограбление произошло в субботу. Если у преступника был ключ, и ограбление произошло в субботу, то сторож не выходил на работу. Следовательно, если сторож выходил на работу, то у преступника не было ключа.
16. а) Если число векторов совпадает с рангом системы, то система векторов линейно независима и является базисом. Если система векторов линейно независима или является базисом, то число векторов в системе совпадает с ее рангом. Следовательно, система векторов линейно независима тогда и только тогда, когда число векторов в ней совпадает с рангом системы.
б) Целое число делится на 6 тогда и только тогда, когда оно делится на 2 и на 3. Если данное число делится на 2, то оно не делится на 3. Следовательно, данное число не делится на 6.
17. а) Если производная функции в точке равна нулю и при переходе через нее меняет знак с плюса на минус, то данная точка является точкой максимума функции. Если производная в точке равна нулю и эта точка является точкой максимума функции, то производная при переходе через нее меняет знак с плюса на минус. Следовательно, если производная в точке равна нулю, то точка является точкой максимума тогда и только тогда, когда производная при переходе через нее меняет знак с плюса на минус.
б) Параллелограмм является прямоугольником тогда и только тогда, когда его диагонали равны. Диагонали параллелограмма равны тогда и только тогда, когда все его углы равны между собой. Следовательно, параллелограмм является прямоугольником тогда и только тогда, когда диагонали или все его углы равны.
18. а) Система линейных уравнений разрешима и имеет единственное решение тогда и только тогда, когда число неизвестных совпадает с рангом системы. Число неизвестных данной системы линейных уравнений не совпадает с рангом системы. Следовательно, если система линейных уравнений разрешима, то она имеет неединственное решение.
б) Если музыкант принесет ноты, то мы пойдем на его концерт, если инструмент будет настроен. Если инструмент будет настроен, то музыкант принесет ноты, если мы придем на его концерт. Инструмент будет настроен. Следовательно, мы придем на концерт тогда и только тогда, когда музыкант принесет ноты.
19. а) Параллелограмм является ромбом тогда и только тогда, когда все его стороны равны. Если диагонали параллелограмма перпендикулярны, то этот параллелограмм – ромб. Следовательно, параллелограмм является ромбом, если все его стороны равны или диагонали перпендикулярны.
б) Известно, что свидетель ошибся или злоумышленник не уехал в экипаже. Если злоумышленник имел сообщника, то он уехал в экипаже. У злоумышленника не было ни сообщника, ни ключа или у него был сообщник и был ключ. Следовательно, если у злоумышленника был ключ, то свидетель ошибся.
20. а) Треугольник является равнобедренным тогда и только тогда, когда его боковые стороны равны. Если боковые стороны треугольника равны, то равны и углы при основании. Следовательно, треугольник является равнобедренным тогда и только тогда, когда его боковые стороны и углы при основании равны.
б) Если я сдам все зачеты и экзамен по логике, то пойду на свидание. Если я сдам экзамен по логике и не пойду на свидание, то я сдам все зачеты. Следовательно, либо я пойду на свидание, либо не сдам экзамен по логике.
21. а) Число делится на 3 тогда и только тогда, когда сумма его цифр в десятичной записи делится на 3. Если число делится на 9, то оно делится на 3, Следовательно, если число делится на 9, то сумма его цифр в десятичной записи делится на 3.
б) Если функция дифференцируемая и ее производная монотонно возрастает, то функция является выпуклой вниз. Если функция дифференцируемая и является выпуклой вниз, то ее производная монотонно возрастает. Следовательно, если функция дифференцируемая, то она является выпуклой вниз тогда и только тогда, когда ее производная монотонно возрастает.
22. а) Четырехугольник является квадратом или ромбом тогда и только тогда, когда все его стороны равны. Четырехугольник не является квадратом. Следовательно, четырехугольник является ромбом тогда и только тогда, когда все его стороны равны.
б) Если матрица А – невырожденная, то ее определитель отличен от нуля, а ее строки образуют линейно независимую систему векторов. Если определитель отличен от нуля, то матрица А – невырожденная и ее строки образуют линейно независимую систему векторов. Следовательно, определитель отличен от нуля тогда и только тогда, когда матрица А является невырожденной и ее строки образуют линейно независимую систему векторов.
23. а) Четырехугольник является ромбом тогда и только тогда, когда он является квадратом или когда все его стороны равны. Если четырехугольник является квадратом, то все его стороны равны. Следовательно, четырехугольник является ромбом тогда и только тогда, когда все его стороны равны.
б) Если последовательность монотонная и ограниченная, то она имеет предел. Если последовательность монотонная и имеет предел, то она ограничена. Следовательно, если последовательность монотонная, то она ограничена тогда и только тогда, когда имеет предел.
24. а) Четырехугольник является параллелограммом тогда и только тогда, когда его противоположные стороны попарно параллельны. Четырехугольник является параллелограммом тогда и только тогда, когда его диагонали в точке пересечения делятся пополам. Следовательно, четырехугольник является параллелограммом тогда и только тогда, когда его противоположные стороны попарно параллельны или когда его диагонали в точке Пересечения делятся пополам.
б) Система линейных уравнений разрешима и имеет единственное решение тогда и только тогда, когда число неизвестных совпадает с рангом системы. Данная система линейных уравнений имеет неединственное решение. Следовательно, число неизвестных данной системы не совпадает с рангом.
25. а) Если прямая l перпендикулярна прямым а и b, то прямые а и b параллельны. Если l перпендикулярна прямой b и прямые а и b параллельны, то l перпендикулярна а. Следовательно, если l перпендикулярна прямой b, то прямые а и b параллельны тогда и только тогда, когда l перпендикулярна прямой а.
б) Два множества равны друг другу тогда и только тогда, когда они состоят из одних и тех же элементов. Следовательно, два множества не равны друг другу тогда и только тогда, когда они не состоят из одних и тех же элементов.
Формула Н является логическим следствием формул , если из одновременной истинности формул следует истинность формулы Н. Таким образом, если построить таблицу истинности формул , H, то в строках таблицы, в которых все формулы одновременно истинны, формула Н, если она является следствием ,обязана также быть истинной. В этом случае пишут ˫ H.
При дедуктивных рассуждениях, когда из некоторых суждений выводится умозаключение, говорят, что умозаключение правильное, если оно является логическим следствием данных суждений.
Проверить правильность умозаключения можно методом от противного. Мы предполагаем, что Н не является логическим следствием . Тогда должна быть ситуация, при которой H = 0, a все одновременно истинны. Если во всех случаях, при которых H = 0,по крайней мере, одна из формул ложная, то мы приходим к противоречию, и умозаключение правильное. Если же хотя бы в одном случае мы найдём, что все истинны, то умозаключение не является правильным.
Пример. Проверить правильность умозаключения методом от противного:
"Если завтра будет холодно, то я надену теплое пальто, если рукав будет починен. Завтра будет холодно, а рукав не будет починен. Следовательно, я не надену теплое пальто".
Решение. Используя аппарат алгебры высказываний, запишем наши высказывания в виде выражений, использующих обозначения логических операций и простых высказываний. Обозначения:
1) завтра будет холодно – а;
2) я надену тёплое пальто – b;
3) рукав пальто будет починен – с.
Заданные суждения:.
Умозаключение:.
Пусть . Если , то а = 1, с = 0. Тогда .
Отсюда следует, что умозаключение правильное.
Задача 6
Упростите РКС так, чтобы она содержала не более N контактов.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
; б) 
.
. Преобразование (2) осуществляется с использованием дистрибутивности операции & относительно Ú к двум первым скобкам.
; б) 
;
; г) 
.
, если из одновременной истинности формул 
˫ H.
.
.
. Если 
, то а = 1, с = 0. Тогда 
.
