Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

14. Для каждой ли пропозициональной формы существует равносильная ей с.к.н.ф.? Единственна ли с.к.н.ф. для заданной формы? Упражнения 1. Какие из следующих предложений являются высказываниями: а) 2x2=4; б) 2 - простое число; в) город Париж находится в Азии; г) 3> 5; д) 3+5; е) Зх=2; ж) числа вида 2^ 1, где р - простое число, назовем числами Мерсенна; з) остаток от деления на 7 числа 3, возведенного в степень 123 456 789 равен 6; и) является ли число 12345678998765432111111111111 простым? 2. Следующие предложения являются составными высказываниями. Найдите их простые компоненты, т.е. такие высказывания, которые не построены из каких-либо других высказываний: а) 7 - простое число и не делится на 5; б) число 2^^^^^ - 1 простое и его запись содержит более 3376 цифр; в) города Самара и Казань расположены на берегу Волги; г) слово «алгоритм», которое иногда пишут «алгорифм», происходит от имени арабского математика аль-Хорезми, который в IX столетии внес значительный вклад в распространение существовавших тогда методов вычислений; д) число вида аЪа ЪаЪ делится на 7, так как такое число является произведением чисел cfZ^nlOlOl, а сомножитель 10101 кратен 7. 3. Пусть А ж В обозначают соответственно «Андрей студент» и «Борис студент». Запишите приведенные далее высказывания в символической форме, т.е. используя только обозначения для высказываний (А,В), символы v,=>,= и скобки: а) Андрей - студент и Борис - не студент; б) Борис - студент, а Андрей - не студент; в) Андрей и Борис оба не студенты; г) Андрей или Борис студент; д) либо Андрей - студент, либо Борис - студент; е) ни Андрей, ни Борис не студенты; ж) Андрей не студент и Борис не студент; з) неверно, что Андрей и Борис оба студенты; и) Андрей студент тогда и только тогда, когда Борис студент. 21