Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 10

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 4 5 6 7 8 9 < 10 > 11 12 13 14 15 16 .. 101 >> Следующая


Пусть эта функция определяет некоторый эндоморфизм свободной полугруппы; иначе говоря,

<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 действительно вы водимо из р).
Предыдущая << 1 .. 4 5 6 7 8 9 < 10 > 11 12 13 14 15 16 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed