Алгоритмическое определение булевских операций

Отрицание

Конъюнкция

a) b)

Эти 2 определения блок-схем не эквивалентны, если рассматривать неопределенное значение переменных.

b₁=false b₂=0.

Вторая блок-схема соответствует классическому определению конъюнкции: если хотя бы один из элементов функции не определен, то и функция не определена.

Вариант «а» дает так называемое быстрое означивание конъюнкции. Строго говоря, это другая, отличная от конъюнкции операция, которая часто обозначается “cand” или условный (conditional and, но не в паскале). В паскале обозначение and используется для обеих операций. Точная семантика реализуется директивой компилятора. {$B±}

Пример: найти номер заданного значения в последовательности из n чисел

Вариант 1

i:=1; while (i≤n) and (a[i]=x) do i:=i+1;

1. i:=1; read(a); while (i≤n) and (a=x) do begin

read(a);

i:=i+1;

end;

2. i≤n) and (a[i]=x)

Рекомендации: не полагаться на разную семантику булевских операций, не допускать неопределенности выражений. Те же соображения приложимы к определению дизъюнкции, true or 0.

Замечания по программированию условий:

Упрощение отрицания not(not­­_b)=b

not(b₁ and b₂)=not b₁ or not b₂

not(b₁ or b₂)=not b₁ and not b₂

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

Пример: линейный поиск.

Program poisk4(input,output);

Var a,x:integer;

found:boolean;

begin

found:=false;

read(x);

while not eof() and not found do

begin

read(a);

if x=a then found:=true;

end;

end.

Стратегия вычисления условий

Написание достаточно сложных условий само по себе требует некоторой системы.

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

b:= (принадлежит сектору 1) or (принадлежит сектору 2) or (принадлежит треуг)

Принадлежит сектору 1:= (y>=x+1) and (sqr(x)+sqr(y)<=1)

Принадлежит сектору 2:= (y>-x-1) and (sqr(x)+sqr(y)<=1).

Принадлежит треугольнику:= (abs(y)<=x) and (x<=1).

Замечание: эта стратегия иллюстрирует важный факт в математической логике. Любое свойство можно записать в виде дизъюнкции элементарных конъюнкций.

Вычисление кванторов

Полный язык математической логики содержит кроме перечисленных выше булевских операций кванторные операции.

Зафиксируем некоторое перечисление элементов множества X:

X={x₁, x₂, x₃, …}

x X B(x)=B(x₁) and B(x₂) and B(x₃) …

x X B(x)=B(x₁) or B(x₂) or B(x₃) …

Рекуррентное определение кванторов

{b=xX B(x)}

b₀:=true

b_i+1:=b_i and b(x_i+1)

b:=true

i:=1

while (i<=n) and b do begin

if not B(x_i+1) then b:=false;

i:=i+1;

end;

Выяснить, является ли данная последовательность упорядоченной

Begin

assign(f,’input.txt’);

reset(f);

b:=true;

if eof(f)=false then

begin

read(f,ao);

while(eof(f)=false) and b do

begin

read(f,a);

if ao<=a then ao:=a

else b:=false;

end;

end;

writeln(b);

close(f);

End.

Пример вычисления квантора существования – задача поиска.

b:=  i[1..n] (x=a_i