Математическая логика и теория алгоритмов

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