Вопрос 22: Простые и сложные высказывания. Логические операции над высказываниями.
«Высказывание – утверждение,
относительно которого можно
сказать, истинно оно или ложно»
И.Л.Батаронов.
Простые высказывания – высказывания типа 5>3. Главное свойство простого высказывания – его истинность или ложность. Из простых высказываний с помощью некоторых логических операций можно строить сложные высказывания, причем они также будут истинными или ложными, это зависит только от истинности или ложности образующих простых высказываний и использованных логических операций.
Истинность обозначают – «1», ложность –«0».
Логические операции определяются с помощью таблиц истинности, связывающих значения истинности простых высказываний и результирующего сложного высказывания.
1) отрицание или инверсия, «не», not, ¯
|
a |
not a |
|
0 |
1 |
|
1 |
0 |
Операция унарная
2) Конъюнкция (логическое и), или логическое умножение.
And, *, ^,и
|
a |
b |
a and b |
|
0 |
0 |
0 |
|
1 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
1 |
1 |
3) Дизъюнкция (логическое или), логическое сложение.
V, +, or
|
a |
b |
a or b |
|
0 |
0 |
0 |
|
1 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
1 |
1 |
4) Строгая дизъюнкция (сложение по модулю)
vv,
,xor
|
a |
b |
a xor b |
|
0 |
0 |
0 |
|
1 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
1 |
0 |
5)Эквивалентность<->,~
|
a |
b |
a ~ b |
|
0 |
0 |
1 |
|
1 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
1 |
1 |
6) Штрих Шеффера (несовместность), «И НЕ»
|
a |
b |
a |b |
|
0 |
0 |
1 |
|
1 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
1 |
0 |
7) Стрелка Пирса, «или не», ↓
|
a |
b |
a ↓ b |
|
0 |
0 |
1 |
|
1 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
1 |
0 |
8) Импликация →, [С в обратную сторону]
|
a |
b |
a → b |
|
0 |
0 |
1 |
|
1 |
0 |
1 |
|
0 |
1 |
0 |
|
1 |
1 |
1 |
Используя рассмотренные операции можно строить сколь угодно сложные высказывания, учитывая при этом следующее:
Приоритет операции, логические операции имеют следующий приоритет по убыванию: самый большой приоритет у отрицания, конъюнкция и Штрих Шеффера, Дизъюнкция и стрелка Пирса, Импликация, Эквивалентность.
Операции одинакового приоритета выполняются слева на право.
Операции в скобках выполняются в первую очередь.
Билет №27. Записи в Паскале. Определения, назначение и использование.
Тип записи.
Запись – тип данных, объединяющий фиксированное число элементов различного типа. Элементы, входящие в состав записи называются полями записи. Каждое поле имеет собственное имя, используемое для доступа к данному элементу. Поэтому можно выделить любой элемент записи и обращаться с ним как с отдельной переменной.
Формат:
Type
Имя = record
Имя_поля1: тип_поля1;
…
Имя_поляn: тип_поляn;
End;
В качестве типов полей могут выступать скалярный тип, массив, строка, другая запись или указатель. В свою очередь запись может являться базовым типом массива.
Пример: запись, содержащая сведения о книге.
Type
Book = record;
Title:string[100];
Author:string[40];
Year:integer;
End;
Над записями допустимы операции присваивания, проверки на (не)равенство, ввода, вывода. С любым полем записи можно обращаться как с переменной соответствующего типа. Обращение к полю по составному имени – имя_записи.имя_поля.
Пример:
Type
Book = record;
Title:string[100];
Author:string[40];
Year:integer;
End;
Var x,y:book;
Z:array[1..100] of Book;
Begin
x.title:=’Война и мир’;
x.author:=’Толстой Л.Н.’;
x.year:=1980;
y:=x;
writeln(x.title, y.author); z[5]:=x;
end.
Если поле является записью, то обращение к его элементам будет производиться по имени, состоящему из 3 частей. Глубина вложения не ограничена.
Пример: сформировать массив записей с информацией о данных экзаменах и вычислить средний балл.
Const number_subject = 3;
Number_student = 20;
Type student = record;
Name:string;
Subject:array[1..Number_subject] of record;
Title:string;
Mark:integer;
End;
End;
Group = array[1..number_student] of student;
Course = record;
Kb:group;
Ib:group;
Bt:group;
End;
Var fisrt_course:course;
I,j,summa:integer;
Mean:real;
Begin
First_course.ib[1].name:=’Иванов’;
First_course.ib[1].subject[1].title:=’’ВВС’;
First_course.ib[1].mark:=3;
First_course.ib[1].subject[2].title:=’Информатика’;
First_course.ib[1].mark:=4;
…
summa:=0;
for I:=1 to number_student do begin
for j:=1 to number_subject do begin
if first_course.ib[1].subject[I].title = ‘ВВС’ then
summa:= summa + first_course.ib[I].subject.mark;
end;
end;
mean:=summa/number_student;
writeln(mean);
end.
Оператор with.
Оператор with позволяет сократить обращение к полям записи
Формат: with имя_записи do оператор;
В качестве оператора может использоваться составной, внутри него можно пропускать имя записи в составном имени поля.
Пример:
Var x:book;
Begin
…
with x do begin
read(title, Author);
writeln(title, Author);
end;
…
end.
Последовательный поиск в массиве записей
Массивы записей удобно использовать для хранения больших объемов разнородной информации. Часто возникает задача поиска элемента массива, одно из полей которого имеет заданное значение. Самый простой алгоритм поиска – последовательный поиск. Состоит в том, что у всех записей последовательно, начиная с первой проверяется значение признака, по которому ведется поиск.
Пример:
Type
Book = record;
…
catalog = array[1..100] of book;
var
cat:catalog;
s:string;
i:integer;
begin
read(s);
i:=1;
while (i<=100) and (cat[i].author<>s)
do i:=i+1;
if cat[i].author = s then writeln(i);
else writeln(‘Нет’);
end.
Двоичный поиск в массиве записей.
Общим свойством алгоритмов последовательного поиска является то, что t поиска прямо пропорционально количеству записей. Если массив предварительно отсортировать по значению признака поиск можно производить быстрее.
Пример: найти книгу нужного автора в каталоге упорядоченном по фамилиям.
открыть каталог посередине;
сравнить искомую фамилию с той, что в середине;
если совпадает - поиск завершен;
если фамилия в середине позже искомой – продолжить поиск в первой половине каталога, иначе – во второй.
Продолжить поиск означает повторять все шаги заново. В конце концов запись либо будет найдена, либо, когда нечего делить, можно сказать, что записи нет.
Пример:
Type book = record;
…
catalog = array[1..100] of book;
var cat:catalog;
s:string;
i,j,k,m:integer;
begin
read(s);
i:=1; j:=100; k:=0;
while (k=0) and ((j-i)>1) do begin
m:=(i+j)div2;
if(cat[m].author = s) then k:=m
else
if cat[m].author<s
then i:=m
else j:=m;
end;
if (k=0) and (cat[i].author = s) then k:=i;
if (k=0) and (cat[j].author = s) then k:=j;
if k<>0 then writeln(k)
else writeln(‘Книги нет’);
end.
При последовательном поиске область сокращается на одну запись за каждый шаг алгоритма, при двоичном сокращается в два раза, значит, при удвоении числа записей время последовательного поиска возрастет в два раза, а двоичного – на один шаг алгоритма.