Определение 3.1:  Пусть дано конечное множество М = {n₁, n₂,.., n_k}. Назовем множество {x₁,{x₂,{x₃,..{x_p}...}}}, где x_i M, цепочкой длины p из множества M (f[1,p]=<x₁,x₂,x₃,..x_p>. Множество М в этом случае называют алфавитом, а его элементы - буквами (символами). Из определения понятно, что буквы могут входить в цепочку больше одного раза. Символ, стоящий на i-ом месте цепочки f, будем обозначать через f[i], а подцепочку <x_i,x_i+1,..x_k>, цепочки f через f[i,k]. Пустую цепочку (длины 0) мы будем обозначать через L.

Примечание 1. Любую цепочку в два элемента будем называть упорядоченной парой, из трех элементов - упорядоченной тройкой, из четырёх - упорядоченной четвёркой и т. д.

Определение 3.2:  Пусть даны две цепочки f[1,p]=<x₁,x₂,x₃,..x_p> и g[1,k]=<y₁,y₂,y₃,..y_k>.
· Конкатенацией цепочки f с цепочкой g называется цепочка f+g = <x₁,x₂,..x_p,y₁,y₂,..y_k>.
    Например, <a,b,c> + <b,c> = <a,b,c,b,c>.
· Подстановкой цепочки f в цепочку g вместо подцепочки g[i,m], где 1imk, называется цепочка S(f,g,i,m) = g[1,i-1] + f[1,p]+g[m+1,k]. Например, S(<a,b,c,d>,<u,u>,2,3)=<a,u,u,d>.

Определение 3.3:  Назовем упорядоченную четверку Г=<V,W,I,R> формальной грамматикой, где W – некоторый алфавит, который мы будем называть алфавитом вспомогательных символов, V – алфавит, который называется алфавитом основных символов, II W, называемый начальным символом. R – множество правил вывода грамматики, то есть множество пар цепочек, составленных из алфавита VW, вида fg. В правиле fg цепочка f называется левой частью, g – правой частью.
    Правило вывода определяет подстановку цепочки g вместо цепочки f.
    К цепочке x[1,n] применимо правило fg только тогда, когда f=x[i,k] (f – подцепочка x), и результатом применения правила будет цепочка S(x,g,i,k).Мы будем говорить, что цепочка g выводима из f в грамматике Г, если существует такая цепочка цепочек x₁,x₂,..x_n, что x₁=f и x_n=g, и для каждой пары <x_i,x_i+1> существует такое правило rI R, что x_i+1 является результатом применения этого правила к x_i.
   Замыканием цепочки f (обозначается f⁺(R)) относительно правил грамматики Г называется множество всех выводимых из f цепочек.

Определение 3.4: Языком грамматики Г=<V,W,I,R> назовем множество цепочек L(Г)=I⁺(R).

1. Пусть дана цепочка f длины n, состоящая из одинаковых символов. Какой длины будет цепочка, полученная конкатенацией всех различных подцепочек цепочки f (подцепочки из одинаковых элементов, стоящих на разных местах, считаются одинаковыми).
2. Постройте грамматики, порождающие следующие языки:

a). {a,b}	c). L1={ab,abab,ababab,...}	e). L1L2
b). {a,aa,aaa,aaaa,...}	d). L2={b,aba,aabaa,...}

3. Постройте грамматику, порождающую числа натурального ряда {1,2,3,..10,11,12,..}.
4. Постройте грамматику <V,W,I,R>, порождающую все перестановки цепочки abcd, в которой меньше 20 правил (число элементов множества R).

Определение 3.5: Язык логики высказываний порождается грамматикой PL = <V,W,I,R>, где V состоит из элементов следующих классов:

1. Пропозициональные переменные, которые мы будем обозначать через p,q,r (быть может, с нижними индексами).
2. Логические связки: .
3. Скобки (,).

Алфавит вспомогательных символов W={I}, а множество R состоит из следующих правил:

1. I x, для всех пропозициональных переменных,
2. I (II), I (II), I (II), I I.

Цепочки языка логики высказываний называются правильно построенными выражениями (формулами)

Определение 3.6: Подформулой формулы F называется любая цепочка символов, входящая в формулу F, которая сама является формулой.

5. Проверьте являются ли формулами следующие выражения:

   а). ((pq) (qp))

   b). ((pq) p)

6. Выпишите все подформулы формул:

   а). (((pq) (qr)) (p r))

   b). ((pq) ((p q) q)

7. Сколькими способами можно расставить скобки в последовательности, чтобы получилась формула:

Каждой пропозициональной переменной некоторой формулы f может быть приписано истинностное значение 1 (истина), 0 (ложь), после этого мы можем вычислить значение формулы f (тоже 1 или 0) по правилам изложенным ниже. Назовем p, (pq), (pq), (pq), соответственно, отрицанием p, конъюнкцией p и q, дизъюнкцией p и q, и импликацией q из p и охарактеризуем их следующими свойствами:

1. формула (pq) истинна тогда и только тогда, когда p и q одновременно истинны,
2. формула (pq) ложна тогда и только тогда, когда p и q одновременно ложны,
3. формула (pq) ложна тогда и только тогда, когда p истинна и q ложна,
4. формула p истинна тогда и только тогда, когда p ложна.

Следующие истинностные таблицы определяют логические связки :

p p 0 1 1 0	q   0 1 p 0 0 0   1 0 1
q   0 1 p 0 1 1   1 0 1	q   0 1 p 0 0 1   1 1 1

Используя эти четыре таблицы, можно построить оценку любой формулы языка логики высказываний следующим образом:

Например построим оценку для формулы (pq) p:

(p q) p	Результат
(1 1) 1 (1 0) 1 (0 1) 0 (0 0) 0	1 1 0 1

Определение 3.8: Формула логики высказываний называется тавтологией (противоречием), если значение этой формулы 1 (0) при любом способе приписывания истинностных значений пропозициональным переменным.

8. Построить оценку следующих формул:

   a). ((pq)(p(qp)))

   b). ((p(qp))(pr))

   c). ((p(qp))((qp)q))

9. Доказать, что формулы являются тавтологиями:

   a). ((pq)(qp))

   b). (p p)

   c). ((pq) ((qr) (pr)))

10. При каких значениях переменных p, q формула ((pq) ((pq) (pq))) ложна ?
    
11. Сколькими способами можно приписать истинностные значения (0 или 1) формуле, в которой встречается n разных пропозициональных переменных ?

[Вернутся к оглавлению]