Логические основы компьютера

Лабораторная работа

Алгебра логики — это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Логическое высказывание — это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Так, например, предложение «6 — четное число» следует считать высказыванием, так как оно истинное. Предложение «Рим — столица Франции» тоже высказывание, так как оно ложное.

Разумеется, не всякое предложение является логическим высказыванием. Выска­зы­ва­ниями не являются, например, предложения «студент первого курса» и «информатика — интересный предмет». Первое предложение ничего не утверждает о студенте, а второе использует слишком неопределённое понятие «интересный предмет». Вопросительные и восклицательные предложения также не являются высказываниями, поскольку говорить об их истинности или ложности не имеет смысла.

Предложения типа «в городе A более миллиона жителей», «у него голубые глаза» не являются высказываниями, так как для выяснения их истинности или ложности нужны дополнительные сведения: о каком конкретно городе или человеке идет речь. Такие предло­жения называются высказывательными формами.

Высказывательная форма — это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями.

Алгебра логики рассматривает любое высказывание только с одной точки зрения — является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания. Так, например, высказывание «площадь поверхности Индийс­кого океана равна 75 млн кв. км» в одной ситуации можно посчитать ложным, а в другой — истинным. Ложным — так как указанное значение неточное и вообще не является постоянным. Истинным — если рассматривать его как некоторое приближение, приемлемое на практике.

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

Bысказывания, образованные из других высказываний с помощью логических свя­зок, называются составными. Высказывания, не являющиеся составными, называются элементарными.

Так, например, из элементарных высказываний «Петров — врач», «Петров — шахматист» при помощи связки «и» можно получить составное высказывание «Петров — врач и шахматист», понимаемое как «Петров — врач, хорошо играющий в шахматы».

При помощи связки «или» из этих же высказываний можно получить составное высказывание «Петров — врач или шахматист», понимаемое в алгебре логики как «Петров или врач, или шахматист, или и врач и шахматист одновременно».

Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание «Артём поедет летом на море», а через В — высказывание «Артём летом отправится в горы». Тогда составное высказывание «Артём — логическая связ­ка, А, В — логические переменные, которые могут принимать только два значения — «истина» или «ложь», обозначаемые, соответственно, "1" и "0".

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение:

НЕ Операция, выражаемая словом «не», называется отрицанием и обозначается чертой над высказыванием (или знаком ­^┐). Высказывание истинно, когда A ложно, и ложно, когда A истинно.

Пример. «Луна — спутник Земли» (А); «Луна — не спутник Земли» (^┐ А).

И Операция, выражаемая связкой «и», называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой «●» (может также обозначаться знаками ^ или &). Высказывание А●В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Например, высказывание «10 делится на 2 и 5 больше 3» истинно, а высказывания " 10 делится на 2 и 5 не больше 3 ", "10 не делится на 2 и 5 больше 3", " 10 не делится на 2 и 5 не больше 3 " — ложны.

ИЛИ Операция, выражаемая связкой «или» (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны.

Например, высказывание «10 не делится на 2 или 5 не больше 3» ложно, а высказывания "10 делится на 2 или 5 больше 3 ", " 10 делится на 2 или 5 не больше 3 ", " 10 не делится на 2 или 5 больше 3 " — истинны.

ЕСЛИ-ТО Операция, выражаемая связками " если..., то ", " из... следует ", "... влечет... ", называется импликацией (лат. implico — тесно связаны) и обозначается знаком →. Высказывание А→В ложно тогда и только тогда, когда А истинно, а В ложно.

Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний:

«данный четырёхугольник — квадрат» (А) и «около данного четырёхугольника можно описать окружность» (В).

Рассмотрим составное высказывание А→В, понимаемое как «если данный четырёхугольник квадрат, то около него можно описать окружность». Есть три варианта, когда высказывание А→В истинно:

· А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;

· А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);

· A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность.

Ложен только один вариант, когда А истинно, а В ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность.

В обычной речи связка «если..., то» описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться "бессмысленностью" импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, такими: " если президент США — демократ, то в Африке водятся жирафы", " если арбуз — ягода, то в бензоколонке есть бензин ".

Таким образом, операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания.

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

1. Операция отрицания (НЕ)

2. Конъюнкция (И)

3. Дизъюнкция (ИЛИ)

4. Импликация.

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

Математический аппарат алгебры логики с двумя значениями логических пере­менных (1,0) применяется для описания функционирования аппаратные средства компью­тера, в основе которого двоичная система счисления. А также, одни и те же устройства компьютера могут применяться для обработки и хранения как числовой информации, представленной в двоичной системе счисления, так и логических переменных.

Принято значения логических функций записывать в виде таблиц (таблиц истинности). Число строк в такой таблице – это число возможных наборов значений аргументов (2ⁿ, где n - число переменных). Таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.

Таблица истинности для отрицания переменной А.

Таблицы истинности функции двух переменных, связанных связками И (^), ИЛИ (v):

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

Поиск по сайту: