Вернуться к списку примеров

Элементы математической логики
(материал разработан с участием студентки ЗГУ О.Ганюк)

В GAP имеются две логические константы - true (истина) и false (ложь). Их значения можно присваивать переменным:
gap> A:=true;
true
gap> B:=false;
false    
Система GAP позволяет определять истинность тех или иных выражений:
gap> 2+2=5;
false
gap> 1/2 in Integers; # 1/2 не содержится в множестве целых чисел
false
gap> 15 mod 5 = 3;    # остаток от деления 15 на 5 не равен 3
false
gap> 16 mod 5 = 1;    
# остаток от деления 16 на 5 равен 1
true
gap> 1+(1/10000) > 1;
true
Над логическими константами можно выполнять операции отрицания, конъюнкции и дизъюнкции. Рассмотрим примеры вычисления для заданных выше переменных А и В, равных соответственно true и false.
gap> A or B;
true
gap> A and B;
false
gap> not A;
false
gap> not B;
true
Для более сложного логического выражения зададим переменную С со значением true:
gap> C:=true;
true
gap> (A and B) or C;
true
Построим таблицу истинности для логических операторов and и or. Сначала зададим список h, состоящий из всевозможных комбинаций true и false, следующим образом:
gap> h:=[[true,true],[true,false],[false,true],[false,false]];
[ [ true, true ], [ true, false ], [ false, true ], [ false, false ] ]
Теперь будем перебирать все пары из этого списка с помощью цикла forod. Для каждой пары (x1,x2) выведем на печать значение высказываний "А и В", "А или В", "не А", "не В" :    
gap> for x in h do
> Print(x, "  ", x[1] and x[2], "  ", x[1] or x[2], "\n");
> od;
[ true, true ]  true  true
[ true, false ]  false  true
[ false, true ]  false  true
[ false, false ]  false  false

Аналогичным образом построим таблицу истинности для импликации, с учетом логического закона, выражающего ее с помощью отрицания и дизъюнкции :
gap> for x in h do
> Print(x, "  ", not x[1] or x[2], "\n");
> od;
[ true, true ]  true
[ true, false ]  false
[ false, true ]  true
[ false, false ]  true
Следующие команды выводят на экран таблицу истинности для эквиваленции:    
gap> for x in h do
> Print(x, "  ", (not x[1] or x[2]) and (not x[2] or x[1]), "\n");
> od;
[ true, true ]  true
[ true, false ]  false
[ false, true ]  false
[ false, false ]  true
Перебрать всевозможные значения элементарных высказываний, входящих в логическую формулу, можно было бы более эффективно с использованием функции Tuples(list, k), которая возвращает список всевозможных упорядоченных наборов длины k из элементов списка list.

Например, список  h в предыдущем примере можно было создать следующим образом:
gap> Tuples([true,false],2);
[ [ true, true ], [ true, false ], [ false, true ], [ false, false ] ]
Если в логическую формулу входят три элементарных высказывания, то нужно создать список, состоящий из всевозможных упорядоченных троек, элементами которых являются true и false:
gap> s:=Tuples([true,false],3);
[ [ true, true, true ], [ true, true, false ], [ true, false, true ],
  [ true, false, false ], [ false, true, true ], [ false, true, false ],
  [ false, false, true ], [ false, false, false ] ]

Проверим, что элементов списка действительно 8:
gap> Length(s);
8

С помощью этого списка проверим, например, истинность одного из законов де Моргана. Для этого отдельно вычислим левую и правую части соответствующего высказывания, и проверим, что их значения совпадают при любых значениях A, B и C:
gap> for x in s do
> Print(x, "  ", (x[1] or x[2]) and x[3], "  " ,
> (x[1] and x[3]) or (x[2] and x[3]), "\n");
> od;
[ true, true, true ]  true  true
[ true, true, false ]  false  false
[ true, false, true ]  true  true
[ true, false, false ]  false  false
[ false, true, true ]  true  true
[ false, true, false ]  false  false
[ false, false, true ]  false  false
[ false, false, false ]  false  false

В GAP есть также функции ForAll и ForAny, позволяющие записывать высказывания для с применением кванторов, если множество допустимых значений соответствующих переменных конечно. Например, составим список primes, состоящий из первых восьми простых чисел:
gap> primes:=[2,3,5,7,11,13,17,19];
[ 2, 3, 5, 7, 11, 13, 17, 19 ]
Теперь мы можем проверить:
а) действительно ли каждый элемент списка primes является простым числом, применив функцию IsPrime:
gap> ForAll(primes, IsPrime);
true

b) есть ли в списке элемент, остаток от деления которого на 2 равен 0 (т.е. элемент, делящийся на 2):
gap> ForAny(primes, x -> x mod 2 = 0);
true

с) все ли элементы списка не делятся на 2:
gap> ForAll(primes, x -> x mod 2 <> 0);
false

d) есть ли в списке элементы, которые превосходят 20:
gap> ForAny(primes, x -> x > 20);
false


Вернуться к списку примеров