русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Высказывания | Предикаты | Логические функции

ВЫСКАЗЫВАНИЕМ называется повествовательное предложение, которое может быть истинным или ложным. Например, «сегодня хорошая погода». Если любая часть предложения бессмысленна (то есть нельзя сказать, она истинна или ложна), то говорят, что ВЫСКАЗЫВАНИЕ ПРОСТОЕ. Предыдущее предложение именно такое.

Обычно в предложении можно выделить части, сами являющиеся высказываниями, которые соединены союзами «и», «или», «иначе», «если…то…» и т.п. Однако разбиение сложного повествовательного предложения на простые высказывания нужно делать по смыслу, а не по словам. В предложении «в этой аудитории присутствуют студенты и преподаватель» частями-высказываниями являются
(в этой аудитории присутствуют студенты), (в этой аудитории присутствует преподаватель), которые соединены союзом и:
Смысл союза И таков, что значением сложного высказывания будет истина, если истинны оба входящие в него простые высказывания, и ложь, если хотя бы одно простое высказывание ложно. Неправильная форма: (в аудитории присутствуют студенты) и (преподаватель). Здесь вторая скобка не является высказыванием, поскольку она не может быть истинной или ложной.

Правил преобразования сложного предложения в набор простых высказываний, соединенных союзами, не существует. Эта трудность присуща всем естественным языкам, и она сильно затрудняет, в частности, перевод с одного языка на другой. Однако такое преобразование в большинстве случаев легко осуществляет любой человек, владеющий языком. ПРАВИЛО: в сложном высказывании союзы должны стоять только между высказываниями!

Если высказывание содержит переменные, то оно называется логическим выражением или ПРЕДИКАТОМ. Например, (х больше 0). Логическое выражение (предикат) может быть истинным или ложным в зависимости от значения переменной х. Другими словами, предикат – функция от переменных, которая принимает только два значения – {истина, ложь}. Для предикатов используют функциональные обозначения: M(x) = (x>0).

Предикаты позволяют формализовать СВОЙСТВА ПЕРЕМЕННЫХ: M(x) = true означает, что x обладает свойством (x>0), а M(x) = false означает, что х не обладает свойством (x>0).

На Паскале можно написать программу для вычисления значений этого предиката:

function M(x: real):boolean;            int M(float x);
begin M:= (x>0) end;             { if (x>0) return 1;
  else return ; }

БУЛЕВОЙ ПЕРЕМЕННОЙ называется переменная, принимающая значения {истина, ложь}.
БУЛЕВОЙ ФУНКЦИЕЙ называют предикат, у которого переменные булевы.

Такой функцией, например, является сложное высказывание (в аудитории присутствуют студенты) и (в аудитории присутствует преподаватель), в котором первая и вторая скобки рассматриваются как переменные.

Можно также сказать, что булева функция – функция от переменных, принимающих два значения, и множество ее значений состоит из двух элементов. Обычно эти два значения обозначаются либо {0, 1}, либо {false, true}. Обычно обозначение {0, 1} выбирают, если нет опасности смешать логическую истину с числом 1. Если же в тексте употребляются как числа, так и логические значения, то выбирают второе обозначение.

В Паскале есть две логические константы false, true и тип Boolean = {false, true}, с помощью которого можно вводить логические переменные: var x,y: Boolean;

В логике используются союзы И, ИЛИ, НЕТ, ЛИБО…ЛИБО, ЕСЛИ…, ТО…
Смысл этих союзов обычный:

  1. А ИЛИ В истинно, если истинно А или истинно В,
  2. НЕТ А истинно, если А ложно,
  3. ЛИБО А, ЛИБО В истинно, если истинно А или В, но не оба сразу,
  4. ЕСЛИ А, ТО В ложно, если истинно А и ложно В. Во всех остальных случаях это  выражение истинно. Например, ЕСЛИ ложь, ТО В истинно не зависимо от В. Говорят в    связи с этом, что из лжи следует что угодно.

Союзам И, ИЛИ, НЕТ, ЛИБО…ЛИБО в Паскале соответствуют булевы операторы: and, or, not, xor – «и», «или», «не», «разделительное или». Оператор and называется также КОНЪЮНКЦИЕЙ, оператор or – ДИЗЪЮНКЦИЕЙ, оператор not - ОТРИЦАНИЕМ. Выражения вида (x or y),  (x and y), ((x and not(y)) or (not(x) and y)),и т.п. – называются булевыми.
Каждое булево выражение задает булеву функцию. Мы увидим, что верно и обратное: каждая булева функция может быть задана булевым выражением.

Функция f, зависящая от п переменных x1, x2,…, xnназывается булевой, или переключательной, если функция f и любой из ее аргументов  операторы: and, or, not, xor – «и», «или», «не», «разделительное или». Оператор and называется также КОНЪЮНКЦИЕЙ, оператор or – ДИЗЪЮНКЦИЕЙ, оператор not - ОТРИЦАНИЕМ. Выражения вида (x or y),  (x and y), ((x and not(y)) or (not(x) and y)),и т.п. – называются булевыми.

Каждое булево выражение задает булеву функцию. Мы увидим, что верно и обратное: каждая булева функция может быть задана булевым выражением.

Функция f, зависящая от п переменных x1, x2,…, xnназывается булевой, или переключательной, если функция f и любой из ее аргументов  принимают значения только из множества {0, 1}. Аргументы булевой функции также называются булевыми.
Наиболее распространенными способами задания булевых функций являются: табличный, метод перечислений, цифровой эквивалент, аналитический, семантическое дерево.

При табличном способе булева функция f(x1,…, xn) задается таблицей истинности (табл. 1.1), в левой части которой представлены все возможные двоичные наборы длины п, а в правой указывается значение функции на этих наборах.

Таблица  1.1 – Таблица истинности функции f1


x1

x2

x3

f1

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

1

Под двоичным набором  понимается совокупность значений аргументов x1, x2,…, xn булевой функции f. Двоичный набор имеет длину n, если он представленn цифрами из множества {0,1}. В табл. 1. перечислены все двоичные наборы соответственно длины 3.


Иногда двоичные наборы в таблице истинности булевой функции удобно представлять номерами наборов. Запишем аргументы x1, x2,…, xn в порядке возрастания их индексов. Тогда любой двоичный набор  можно рассматривать как целое двоичное число N:

называемое номером набора.. Например, двоичные наборы 0101 и 1000 имеют номера 5 и 8 соответственно. Очевидно, любая булева функция может быть задана перечислением наборов, принимающих единичное значение. Функция f1  может быть представлена следующим образом: f1 ( x1, x2, ,х3) = ( 2, 3, 7)1 .
Булеву функцию, определенную на всех своих наборах, называют полностью определенной. В табл. 1.1 приведен пример полностью определенной булевой функции.
Булеву функцию п переменных называют не полностью определенной или частичной, если она определена не на всех двоичных наборах длины п. Не полностью определенная булева функция не попадает под определение, данное в начале главы, но при произвольном доопределении (на всех наборах, на которых она не определена) это несоответствие снимается.
Легко убедиться, что если булева функция f2 не определена на т=3наборах аргументов, то путем ее доопределения можно получить 2m различных полностью определенных функций. В табл. 1.2 приведен пример не полностью определенной булевой функции четырех переменных.



Таблица 1.2 – Таблица истинности функции f2

x1

x2

x3

х4

f2

0

0

0

0

0

0

0

0

1

0

0

0

1

0

*

0

0

1

1

1

0

1

0

0

0

0

1

0

1

*

0

1

1

0

1

0

1

1

1

0

1

0

0

0

1

1

0

0

1

*

1

0

1

0

0

1

0

1

1

0

1

1

0

0

0

1

1

0

1

1

1

1

1

0

1

1

1

1

1

0

Цифрой эквивалент задания функции получается если выписать значение функции начиная со старших разрядом, а затем полученную двоичную последовательность перевести в десятичное число. Например для таблицы 1.1 значение  f1(x1,х2, x3) представляет собой последовательность 101011002=128 +32 +8 +4 =17210.
Аналитическое представление булевой функции представляет собой логическую формулу. Например аналитическое представление функции f1 (x1,х2, x3) = 1x2 V x2 x3.
Семантическое дерево – это двоичное дерево, корень которого помечен двоичной функцией от n – переменных. Из каждого узла идут по два ребра, соответствующих двум значениям очередной переменной (ноль или один), а 2n листьев помечены соответствующими значениями функции. Удобство этого представления, что для многих функций значения у всех листьев некоторых поддеревьев совпадают и построение некоторых ветвей быстро заканчивается, не доходя до самого нижнего уровня. Семантическое дерево для  f1 (x1,х2, x3) приведено на рис1.1.

Просмотров: 8938

Вернуться в оглавление:Цифровые автоматы




Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.