3. Задан некоторый набор товаров. Определить для каждого из товаров, какие из них имеются в каждом магазине и каких товаров нет ни в одном магазине.

program lab1;

const N=3;

type product = (bread, butter, cheese, milk);

assortiment = set of product;

stor = array[1..n] of assortiment;

var

m1:stor;

x:product;

a,b,c,xm1:assortiment;

i,j,iw,m:integer;

begin

for i:=1 to n do

begin

xm1:=[];

writeln('enter the number of product',i:2,'stor');

repeat

writeln('1: x:=bread; 2: x:=butter; 3: x:=cheese; 4: x:=milk; 5: break');

writeln('Vvedite 1 or 2 or 3 or 4 or 5');

read(iw);

case iw of

1: x:=bread;

2: x:=butter;

3: x:=cheese;

4: x:=milk;

5: break;

end;

xm1:=xm1+[x];

until iw=5;

m1[i]:=xm1;

end;

a:=m1[1];

c:=[bread..milk];

for i:=1 to n do

begin

b:=b+m1[i];

a:=a*m1[i];

c:=c-b;

end;

for i:=1 to 2 do

begin

case i of

1:writeln('products are in all stors:');

2:writeln('products arent in all stors:');

end;

for x:=bread to milk do

if x in a then

case x of

bread:writeln('bread');

butter:writeln('butter');

cheese:writeln('cheese');

milk:writeln('milk');

end;

if i=1 then a:=c;

end;

end.

Билет №3

1. Алгебра высказываний как модель алгебры Буля, ее аксиоматическое задание. Принцип двойственности и теорема двойственности.

Высказыванием называется законченное повествовательное предложение, для кото-рого можно сказать истинно оно или ложно. Высказывание не м/б одновременно и истинным, и ложным.

Высказывания бывают атомарные (неделимые), или элементарные, исходные и сложные (составные).

Из элементарных высказываний с помощью операций над высказываниями или логических связок строят сложные высказывания.

Операции над высказываниями:

1. Операция конъюнкции ( /\ ).

Конъюнкцией двух высказываний, А и В, называется новое высказывание, обозначаемое (A /\ B), которое истинно тогда и только тогда, когда высказывания A и B истинны одновременно, и ложно во всех остальных случаях. Конъюнкции соответствует логическая связка "и".

2. Операция дизъюнкции ( \/ ).

Дизъюнкцией двух высказываний, А и В, называется новое высказывание, обозначаемое (A \/ B), которое истинно только тогда, когда истинно, по крайней мере, одно из высказываний, A или B, и ложно в единственном случае, когда оба высказывания, А и В, ложны. Дизъюнкции соответствует связка "или".

3. Операция следования или импликации ( → )

Импликацией (следованием) двух высказываний, А и В, называется новое высказывание, обозначаемое (A → B), которое ложно тогда и только тогда, когда A - истинно, а B - ложно, во всех остальных случаях высказывание (A→B) истинно. В высказывании (A → B) A - называется посылкой или антецедентом, B - следствием или консеквентом. Импликация (A → B) в разговорной речи имеет несколько разночтений: если A, то B;из A следует B;A влечет B;B следует из A;A достаточно для B;B необходимо для A.

4. Операция эквивалентности ( ↔ )

Эквивалентностью двух высказываний, A и B, называется новое высказывание, обозначаемое (A ↔ B), которое имеет значение ложь тогда и только тогда, когда A - истинно, а B - ложно или A - ложно, а B - истинно. А значение истина тогда и только тогда, когда одновременно оба высказывания, A и B, либо истинны, либо ложны. Эквивалентность (A ↔ B) в разговорной речи имеет несколько разночтений: A необходимо и достаточно для B; A тогда и только тогда, когда B; A эквивалентно B; A равносильно B; из A следует B , а из B следует A.

5. Операция отрицания(¬) Отрицанием высказывания A называется новое высказывание, обозначаемое , которое истинно тогда и только тогда, когда ложно A, и ложно тогда и только тогда, когда A истинно.

Алгеброй Буля называется непустое множество, содержащее, по крайней мере, два элемента и замкнутое относительно 2-ух бинарных операций: /\ и \/, удовлетворяющих законам: коммутативности (1), ассоциативности (2), дистрибутивности конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции (3), идемпотентности (4), сокращения (5), поглощения (6), противоречия для конъюнкции и исключения третьего для дизъюнкции (7), законам де Моргана (8) и закону двойного отрицания (9).

1.

2.

x * ( y * z ) = (x * y) * z

3.

4. x * x = x

x + x =x

5. x * И = x

x + Л = x

6. x * Л = Л

x + И = И _

7. x * x = Л _

x + x = И

8.

9.

10.

Аксиоматический метод. Исчисление высказываний

Способ построения научной теории в виде системы аксиом (постулатов) и правил вывода, позволяющих формальным логическим путем получать утверждения (теоремы) данной теории, называется аксиоматическим методом. Одни из правил:

Правило отделения:

"Если истинно утверждение j и истинно, что из j следует y, то истинно и утверждение y".

Правило силлогизма:

"Если истинно утверждение, что из j следует y, и истинно утверждение, что из y следует x, то истинно и утверждение , что из j следует x"

Правило эквивалентной замены:

"Если утверждение j истинно и в него входит утверждение y, о котором известно, что оно эквивалентно другому утверждению x, то истинно и утверждение, полученное из j заменой любых вхождений y на x"

Это правило аналогично часто используемому в математике правилу замены "на равное"

Правило подстановки:

"Если утверждение j истинно независимо от истинности или ложности входящего в него утверждения y, то истинно и утверждение, полученное из j заменой всех вхождений y на любое утверждение x"

Произвольное правило логического вывода называется корректным, если из истинности его посылок всегда следует истинность заключения.

Принцип двойственности впервые был высказан французом по фамилии Понселе.

Формулы α и α^* называются двойственными, если одна из них получается из другой заменой констант "И" и "Л" на двойственные им константы "Л" и "И" соответственно, и каждой операции /\ на двойственную ей операцию \/ , а \/ - на операцию /\.

Теорема 1.Если α(X₁, X₂, ..., X_n) и α^*(X₁, X₂, ..., X_n) двойственные формулы, то отрицание формулы α(X₁, X₂, ..., X_n) равносильно формуле, полученной из α^*( X₁, X₂, ..., X_n) с помощью замены всех переменных на их отрицание, т.е . ≡ α^*( ₁, ₂, ..., _n).

Теорема двойственности (закон двойственности) (Теорема 2)

Если формулы β(X₁, X₂, ..., X_n).и α(X₁, X₂, ..., X_n) равносильны, то двойственные им формулы β^*( X₁, X₂, ..., X_n).и α^*( X₁, X₂, ..., X_n) тоже равносильны.

β(X₁, X₂, ..., X_n). ≡ α(X₁, X₂, ..., X_n)

β^*(X₁, X₂, ..., X_n). ≡ α^*( X₁, X₂, ..., X_n)

Доказательство.

По условию доказываемой теоремы:

β(X₁, X₂, ..., X_n). ≡ α(X₁, X₂, ..., X_n) (1).

По условию теоремы 1: β^*( ₁, ₂, ..., _n) ≡ β , откуда

β^*( , , ..., ) ≡ β , следовательно

β^*(X₁, X₂, ..., X_n) ≡ β (2).

Аналогично, α^*(X₁, X₂, ..., X_n) ≡ α (3).

Из (1) следует, что β . ≡ α , откуда

β ≡ α (4). По свойству равносильности [β^*(X₁, X₂, ..., X_n) и α^*(X₁, X₂, ..., X_n) равносильны соответственно выражениям β и α , которые явл. равносильными] β^*(x₁, x₂, ..., x_n). ≡ α^*(x₁, x₂, ..., x_n), что и требовалось доказать.

Закон двойственности "наполовину уменьшает работу математикам": если уже доказана некоторая равносильность, то справедливость другой, полученной из первой двойственными преобразованиями, уже не нужно доказывать, она будет выполняться.