Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Пусть эта функция определяет некоторый эндоморфизм свободной полугруппы; иначе говоря,
<p(P-Q) = <p(P).<p(Q),
где точкой обозначена конкатенация.
Доказать, что ф вполне определяется теми значениями, которые она принимает на множестве однобуквенных слов; описать несколько простых классов подобных функций.
12. Пусть имеется ассоциативное исчисление, заданное алфавитом її = {a, b} и следующими соотношениями:
ааа ~ Е; bbbb ~ Е; abb ~ bba; ababa ~ Е\ babab ~ Е.Гл. I. Слова (цепочки). Полугруппы. Языки
29
Будем располагать слова этого исчисления в узлах дерева с корнем в Е, соблюдая лексикографический порядок, т. е. следующим образом:
bab...
Затем будем вычеркивать в этом дереве любое слово, для которого уже записано эквивалентное: например, вычеркнем ааа, так как ааа ^ Е, затем bba, так как bba « abb и т. д.
Найти каноническое представление полученных классов; исследовать факторполугруппу и ядро.
13. Будем рассматривать функции, определенные на свободной полугруппе и принимающие значения в этой полугруппе.
Найти функции а, обладающие свойством
a(P-Q) = a[a(P)-a(Q)].
Напомним, что пример такой функции был дан в п. 1.2.3.
14. Рассмотрим следующий карточный пасьянс (с колодой из 32 карт): карты выкладываются в ряд; если карта оказывается между двумя картами одинаковой масти или одинакового достоинства, ее можно убрать; если две карты одной и той же масти или достоинства оказываются между картами одинаковой масти или одинакового достоинства, их можно убрать.
Исследовать теорию этого пасьянса.Глава II
ОБЩИЕ СВЕДЕНИЯ О ФОРМАЛЬНЫХ СИСТЕМАХ
В этой главе мы намереваемся ввести понятие формальной системы и проиллюстрировать его, описав с формальной точки зрения некоторый вариант исчисления высказываний. Этот пример можно полностью понять, только имея интуитивное представление об исчислении высказываний; поэтому сначала мы дадим его краткое изложение.
§ 2.1. ОПИСАНИЕ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИИ НА ИНТУИТИВНОМ УРОВНЕ
2.1.1. Высказывания
«Журдэн — персонаж «Мещанина во дворянстве»», «Два плюс два — пять»: эти две фразы в кавычках суть высказывания. Первое высказывание истинно, его логическое значение — истина-, второе высказывание ложно, его логическое значение — ложь.
«В этот день шел дождь», «Целое число п является простым» и т. п. — не высказывания, а пропозициональные («высказыватель-ные») переменные, которые в зависимости от обстоятельств могут принимать значения истина или ложь.
Обычно значение истина обозначается единицей, а значение ложь — нулем (некоторые авторы используют обратные обозначения).
Таким образом, пропозициональные переменные суть булевы переменные; к этому факту мы еще вернемся.
Исчисление высказываний не занимается анализом высказываний, а рассматривает их как неразложимые единицы — с точки зрения возможностей по-разному комбинировать их с помощью различных логических операций, к обзору которых мы и перейдем.
Высказывания и пропозициональные переменные мы будем обозначать малыми латинскими буквами р, q, ... .
2.1.2. Конъюнкция
Высказывание «Идет дождь и дует ветер» считается истинным тогда и только тогда, когда одновременно идет дождь и дует ветер. Это высказывание является конъюнкцией высказываний «Идет дождь» и «Дует ветер».
Более точно, конъюнкция двух высказываний (или пропозициональных переменных) р и q есть высказывание (пропозицио-Г л //. Общие сведения о формальных системах
31
нальная переменная), обозначаемое р A q и имеющее в четырех возможных случаях распределения значений р и q следующие логические значения:
P я PAq
0 0 0
0 1 0
1 1 0 1 0 1
Помимо символа Д конъюнкцию обозначают также символами & и • или простым соположением высказываний.
2.1.3. Дизъюнкция
Аналогичным образом вводится понятие дизъюнкции. Дизъюнкция определяется следующей таблицей:
p q pvq
0 0 0
0 1 1
1 1 0 1 1 1
Дизъюнкция р V q считается истинной тогда и только тогда, когда истинно хотя бы одно из высказываний р или q. Дизъюнкция соответствует неразделительному употреблению русского «или» в такой фразе, как «Он дурак или мерзавец» (подразумевается: «А может быть, и то, и другое»).
Дизъюнкцию обозначают иногда также символом +.
2.1.4. Отрицание
Любому высказыванию (пропозициональной переменной) р можно поставить в соответствие высказывание ~1р — его отрицание, которое определяется следующей таблицей:
P 1P
0 1 1 0
Другие обозначения отрицания: р, ~ р, Ир.32
Часть /. Предварительные сведения из логики и алгебры
2.1.5. Импликация
Любой паре высказываний р, q можно поставить в соответствие высказывание pzDq, определяемое следующей таблицей:
P <? р = <?
0 0 1
0 1 1
1 0 0
1 1 1
Напоминаем еще раз, что высказывания р и q не анализируются, их содержание не берется в расчет ни в какой степени, и единственное, что о них известно, — это их логические значения. Поэтому импликация, которая была только что определена, не имеет никакого отношения к причинно-следственной зависимости или к выводу q из р (к доказательству q на основе р). Логический оператор гэ в выражении «р zd q» ни в коем случае нельзя смешивать о метаимпликацией «pz^q» (означающей, что q действительно вы водимо из р).