СВОЙСТВА ЛОГИЧЕСКИХ ОПЕРАЦИЙ

1. Обозначения

1.1. Обозначения для логических связок (операций):

a) отрицание (инверсия, логическое НЕ) обозначается ¬ (например, ¬А);

b) конъюнкция (логическое умножение, логическое И) обозначается /\
(например, А /\ В) либо & (например, А & В);

c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/
(например, А \/ В);

d) следование (импликация) обозначается → (например, А → В);

e) тождество обозначается ≡ (например, A ≡ B). Выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны);

f) символ 1 используется для обозначения истины (истинного высказывания); символ 0 – для обозначения лжи (ложного высказывания).

1.2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) \/ В равносильны, а А /\ В и А \/ В – нет (значения выражений разные, например, при А = 1, В = 0).

1.3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), тождество. Таким образом, ¬А \/ В \/ С \/ D означает то же, что и

((¬А) \/ В)\/ (С \/ D).

Возможна запись А \/ В \/ С вместо (А \/ В) \/ С. То же относится и к конъюнкции: возможна запись А /\ В /\ С вместо (А /\ В) /\ С.

2. Свойства

Приведенный ниже список НЕ претендует на полноту, но, надеемся, достаточно представителен.

2.1. Общие свойства

1. Для набора из n логических переменных существует ровно 2 n различных значений. Таблица истинности для логического выражения от n переменных содержит n+1 столбец и 2 n строк.

2.2.Дизъюнкция

1. Если хоть одно из подвыражений, к которым применяется дизъюнкция, истинно на некотором наборе значений переменных, то и вся дизъюнкция истинна для этого набора значений.
2. Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже истинна.
3. Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже ложна.
4. Значение дизъюнкции не зависит от порядка записи подвыражений, к которым она применяется.

2.3. Конъюнкция

1. Если хоть одно из подвыражений, к которым применяется конъюнкция, ложно на некотором наборе значений переменных, то и вся конъюнкция ложна для этого набора значений.
2. Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то конъюнкция этих выражений тоже истинна.
3. Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то конъюнкция этих выражений тоже ложна.
4. Значение конюнкции не зависит от порядка записи подвыражений, к которым она применяется.

2.4. Простые дизъюнкции и конъюнкции

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

1. Простая конъюнкция принимает значение 1 (истина) ровно на одном наборе значений переменных.
2. Простая дизъюнкция принимает значение 0 (ложь) ровно на одном наборе значений переменных.

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

1. Импликация A →B равносильна дизъюнкции (¬ А) \/ В. Эту дизъюнкцию можно записать и так: ¬А \/ В.
2. Импликация A →B принимает значение 0 (ложь) только если A=1 и B=0. Если A=0, то импликация A →B истинна при любом значении B.

Логика очень древняя наука. Ещё в античные времена была известна формальная логика , позволяющая делать заключения о правильности какого-либо суждения не по его фактическому содержанию, а только по форме его построения. Например, уже в древности был известен закон исключения третьего . Его содержательная трактовка была такова: «Во время своих странствований Платон был в Египте ИЛИ не был Платон в Египте». В такой форме это или любое другое выражение будут правильны (тогда говорили: истинно ). Ничего другого быть не может: Платон либо был, либо не был в Египте - третьего не дано.
Другой закон логики - закон непротиворечивости . Если сказать: «Во время своих странствий Платон был в Египте И не был Платон в Египте», то очевидно, любое высказывание, имеющее такую форму, всегда будет ложно . Если из теории следуют два противоречащих друг другу вывода, то такая теория безусловно неправильная (ложная) и должна быть отвергнута.
Ещё один закон, известный в древности - закон отрицания: «Если НЕ верно, что Платон НЕ был в Египте, то значит, Платон был в Египте».
Формальная логика основана на “высказываниях”. “Высказывание” - это основной элемент логики, определяемый как повествовательное предложение, относительно которого можно однозначно сказать, истинное или ложное утверждение оно содержит.
Например : Листва на деревьях опадает осенью. Земля прямоугольная.
Первое высказывание содержит истинную информацию, а второе - ложную. Вопросительное, побудительное и восклицательное предложения не являются высказываниями, так как в них ничего не утверждается и не отрицается.
Пример предложений, не являющихся высказываниями: Не пейте сырую воду! Кто не хочет быть счастливым?
Высказывания могут быть и такими: 2>1, Н2 О+SO3 =H2 SO4 . Здесь используются языки математических символов и химических формул.
Приведённые выше примеры высказываний являются простыми. Но из простых высказываний можно получить сложные , объединив их с помощью логических связок. Логические связки - это слова, которые подразумевают определённые логические связи между высказываниями. Основные логические связки издавна употребляются не только в научном языке, но и в обыденном, - это “и”, “или”, “не”, “если... то”, “либо... либо” и другие известные нам из русского языка связки. В рассмотренных нами трёх законах формальной логики использовались связки “и”, “или”, “не”, “если... то” для связи простых высказываний в сложные.
Высказывания бывают общими, частными и единичными. Общее высказывание начинается со слов: всё, все, всякий, каждый, ни один. Частное высказывание начинается со слов: некоторые, большинство и т.п. Во всех других случаях высказывание является единичным.
Формальная логика была известна в средневековой Европе, она развивалась и обогащалась новыми законами и правилами, но при этом вплоть до 19 века она оставалась обобщением конкретных содержательных данных и её законы сохраняли форму высказываний на разговорном языке.

В 1847 году английский математик Джордж Буль, преподаватель провинциального университета в маленьком городке Корке на юге Англии разработал алгебру логики .
Алгебра логики очень проста, так как каждая переменная может принимать только два значения: истинно или ложно. Трудность изучения алгебры логики возникает из-за того, что для обозначения переменных принимают символы 0 и 1, которые по написанию совпадают с обычными арифметическими единицей и нулём. Но совпадение это только внешнее, так как смысл они имеют совсем иной.
Логическая 1 означает, что какое-то событие истинно, в противоположность этому логический 0 означает, что высказывание не соответствует истине, т.е. ложно. Высказывание заменилось на логическое выражение, которое строится из логических переменных (А, В, Х, …) и логических операций (связок).
В алгебре логики знаки операций обозначают лишь три логические связки ИЛИ, И, НЕ.
1.Логическая операция ИЛИ . Логическую функцию принято задавать в виде таблицы. В левой части этой таблицы перечисляются все возможные значения аргументов функции , т.е. входные величины , а в правой указывается соответствующее им значение логической функции . Для элементарных функций получается таблица истинности данной логической операции. Для операции ИЛИ таблица истинности имеет вид:

Операцию ИЛИ называют также логическим сложением , и потому её можно обозначать знаком «+».
Рассмотрим сложное единичное высказывание: «Летом я поеду в деревню или в туристическую поездку». Обозначим через А простое высказывание «Летом я поеду в деревню», а через В - простое высказывание «Летом я поеду в туристическую поездку». Тогда логическое выражение сложного высказывания имеет вид А+В , и оно будет ложным только, если ни одно из простых высказываний не будет истинным.
2. Логическая операция И . Таблица истинности для этой функции имеет вид:

Из таблицы истинности следует, что операция И - это логическое умножение , которое ничем не отличается от традиционно известного умножения в обычной алгебре. Операцию И можно обозначить знаком по-разному:

В формальной логике операции логического умножения соответствуют связки и, а, но, хотя.
3. Логическая операция НЕ . Эта операция является специфичной для алгебры логики и не имеет аналога в обычной алгебре. Она обозначается чертой над значением переменной, либо знаком приставки перед значением переменной:

Читается в обоих случаях одинаково «Не А». Таблица истинности для этой функции имеет вид:

В вычислительной технике операцию НЕ называют отрицанием или инверсией , операцию ИЛИ - дизъюнкцией , операцию И - конъюнкцией . Набор логических функций “И”, “ИЛИ”, “НЕ” является функционально полным набором или базисом алгебры логики. С помощью него можно выразить любые другие логические функции, например операции “строгой дизъюнкции”, “импликации” и “эквивалентности” и др. Рассмотрим некоторые из них.
Логическая операция “строгая дизъюнкция” . Этой логической операции соответствует логическая связка “либо... либо”. Таблица истинности для этой функции имеет вид:

Операция “строгая дизъюнкция” выражается через логические функции “И”, “ИЛИ”, “НЕ” любой из двух логических формул:

и иначе называется операцией неравнозначности или “сложения по модулю 2”, так как при сложении чётного количества единиц, результатом будет “0”, а при сложении нечётного числа единиц, результат станет равен “1”.
Логическая операция “импликация” . Выражение, начинающееся со слов если, когда, коль скоро и продолжающееся словами то, тогда, называется условным высказыванием или операцией «импликация». Таблица истинности для этой функции имеет вид:

Операцию “импликация” можно обозначить по-разному:

Эти выражения эквивалентны и читаются одинаково: «Игрек равен импликации от А и В». Операция “импликация” выражается через логические функции “ИЛИ”, “НЕ” в виде логической формулы

Логическая операция “эквивалентность” (равнозначность) . Этой логической операции соответствуют логические связки “если и только если”, «тогда и только тогда, когда». Таблица истинности для этой функции имеет вид:

Операция “эквивалентность” обозначается по-разному. Выражения

обозначают одно и тоже, и можно сказать, что А эквивалентна В, если и только если они равнозначны. Логическая операция “эквивалентность” выражается через логические функции “И”, “ИЛИ”, “НЕ” в виде логической формулы

С помощью алгебры логики можно очень кратко записать законы формальной логики и дать им математически строгое доказательство.

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

Примеры использования основных аксиом и законов:

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

Цифровая эпоха

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

Определение

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

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

Как видим, информатика - это наука, которая отличается широтой исследовательских тем и направлений. В качестве примера можно привести следующие вопросы и задачи: что реально, а что невозможно реализовать в программах (искусственный интеллект, самообучение компьютеров и т. п), как решать различного рода специфические информационные задачи максимально эффективно (так называемая теория сложности вычислений), в каком виде следует сохранять информацию и восстанавливать ее, как наиболее эффективно люди должны взаимодействовать с программами (вопросы пользовательского интерфейса, новых языков программирования и т. п).

Теперь же кратко рассмотрим развитие информатики как науки, начиная с ее истоков.

История

Информатика - это молодая наука, которая возникала постепенно и наиболее сильное развитие получила во второй половине XX века. Очень важна она и в наше время, когда практически весь мир зависим от компьютерных и иных электронных вычислительных технологий.

Началось же все с середины XIX века, когда разными учеными были созданы механические калькуляторы и «аналитические машины». В 1834 году Чарльз Бэббидж начал разработку программируемого калькулятора, и, кстати, именно он впоследствии сформулировал множество основных черт и принципов современного компьютера. Также именно он предложил использовать перфокарты, которые затем были в употреблении вплоть до конца 80-x годов XX века.

В 1843 году Ада Лавлейс создала алгоритм для вычисления чисел Бернулли, и это считается первой в истории компьютерной программой.

Примерно в 1885 году Герман Холлерит создал табулятор - устройство для считывания данных с перфокарт. А в 1937 году, спустя почти сто лет после идей и мечты Бэббиджа, компания IBM создала первый программируемый калькулятор.

В начале 1950-х годов всем стало ясно, что компьютер можно использовать в различных сферах науки и промышленности, а не только как инструмент для математических расчетов. И что только зарождавшаяся тогда информатика - это наука, за которой будущее. А чуть позже она получила статус официальной науки.

Теперь же кратко рассмотрим ее структуру.

Структура информатики

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

Информатика - это наука, изучающая…

На данный момент различают несколько основных ее направлений, которые, в свою очередь, делятся на множество ответвлений. Рассмотрим самые основные:

1. Теоретическая информатика . В ее задачи входит исследование как классической теории алгоритмов, так и ряда важных тем, что имеют связь с более абстрактными аспектами математических вычислений.
2. Прикладная информатика . Это наука, вернее, один из ее разделов, который направлен на то, чтобы выявить определенные понятия в области информатики, которые можно использовать в качестве методов решения каких-то стандартных задач, к примеру, построение алгоритмов, хранение и управление информацией с использованием структуры данных. Кроме этого, прикладную информатику применяют в ряде промышленных, повседневных или научных сфер: биоинформатике, электронной лингвистике и прочих.
3. Естественная информатика . Это направление, которое занимается изучением процессов различной обработки информации в природе, будь то человеческий мозг или же человеческое общество. Ее основы строятся на классических теориях эволюции, морфогенеза и прочих. Помимо них, используются такие научные направления, как исследования ДНК, мозговой активности, теория группового поведения и т. п.

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

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

Отрицание

Перед тем как начать подробно рассматривать конкретные примеры, перечислим основные логические операции в информатике:

• отрицание;
• сложение;
• умножение;
• следование;
• равенство.

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

Для каждого действия, как и в обычной математике, используются следующие знаки логических операций в информатике: ¬, v, &, ->.

Каждое действие возможно описать либо цифрами 1/0, либо просто логическими выражениями. Начнём рассмотрение математической логики с простейшей операции, использующей всего одну переменную.

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

При записи этого выражения используется следующее обозначение "¬A".

Приведём таблицу истинности - схему, которая показывает все возможные результаты операции при любых исходных данных.

То есть, если у нас исходное выражение - истина (1), то его отрицание будет ложным (0). А если исходное выражение - ложь (0), то его отрицание - истина (1).

Сложение

Оставшиеся операции требуют наличия двух переменных. Обозначим одно выражение -

А, второе - В. Логические операции в информатике, обозначающие действие сложения (или дизъюнкция), при написании обозначаются либо словом "или", либо значком "v". Распишем возможные варианты данных и результаты вычислений.

1. Е=1, Н=1 ,тогда Е v Н = 1. Если оба тогда и их дизъюнкция также истинна.
2. Е=0, Н=1 ,в итоге Е v Н = 1. Е=1, Н=0 , тогда Е v Н= 1. Если хотябы одно из выражений истинно, тогда и результат их сложения будет истиной.
3. Е=0, Н=0 ,результат Е v Н = 0. Если оба выражения ложны, то их сумма также - ложь.

Для краткости создадим таблицу истинности.

Дизъюнкция

Е	х	х	о	о
Н	х	о	х	о
Е v Н	х	х	х	о

Умножение

Разобравшись с операцией сложения, переходим к умножению (конъюнкции). Воспользуемся теми же обозначениями, которые были приведены выше для сложения. При письме логическое умножение обозначается значком "&", либо буквой "И".

1. Е=1, Н=1 ,тогда Е & Н = 1. Если оба тогда их конъюнкция - истина.
2. Если хотя бы одно из выражений - ложь, тогда результатом логического умножения также будет ложь.

• Е=1, Н=0, поэтому Е & Н = 0.
• Е=0, Н=1, тогда Е & Н = 0.
• Е=0, Н=0, итог Е & Н = 0.

Конъюнкция

Е	х	х	0	0
Н	х	0	х	0
Е & Н	х	0	0	0

Следствие

Логическая операция следования (импликация) - одна из простейших в математической логике. Она основана на единственной аксиоме - из правды не может следовать ложь.

1. Е=1, Н=, поэтому Е -> Н = 1. Если пара влюблена, то они могут целоваться - правда.
2. Е=0, Н=1, тогда Е -> Н = 1. Если пара не влюблена, то они могут целоваться - также может быть истиной.
3. Е=0, Н=0, из этого Е -> Н = 1. Если пара не влюблена, то они и не целуются - тоже правда.
4. Е=1, Н=0, результатом будет Е -> Н = 0. Если пара влюблена, то они не целуются - ложь.

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

Равенство

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

1. А=1, В=1, тогда А≡В = 1. Человек пьёт таблетки тогда и только тогда, когда болеет. (истина)
2. А=0, В=0, в итоге А≡В = 1. Человек не пьёт таблетки тогда и только тогда, когда не болеет. (истина)
3. А=1, В=0, поэтому А≡В = 0. Человек пьёт таблетки тогда и только тогда, когда не болеет. (ложь)
4. А=0, В=1 ,тогда А≡В = 0. Человек не пьёт таблетки тогда и только тогда, когда болеет. (ложь)

Свойства

Итак, рассмотрев простейшие в информатике, можем приступить к изучению некоторых их свойств. Как и в математике, у логических операций существует свой порядок обработки. В больших логических выражениях операции в скобках выполняются в первую очередь. После них первым делом подсчитываем все значения отрицания в примере. Следующим шагом станет вычисление конъюнкции, а затем дизъюнкции. Только после этого выполняем операцию следствия и, наконец, эквивалентности. Рассмотрим небольшой пример для наглядности.

А v В & ¬В -> В ≡ А

Порядок выполнения действий следующий.

1. В&(¬В)
2. А v(В&(¬В))
3. (А v(В&(¬В)))->В
4. ((А v(В&(¬В)))->В)≡А

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

Решение примера

А	В				(А v(В&(¬В)))->В	((А v(В&(¬В)))->В)≡А
х	о	х	о	х	х	х
х	х	о	о	х	х	х
о	о	х	о	о	х	о
о	х	о	о	о	х	о

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

Заключение

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

Сообщение

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

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

Соответствие между сообщением и содержащейся в нем информацией называется правилом интерпретации сообщения. Это соответствие может быть однозначным и неоднозначным. В первом случае сообщение имеет лишь одно правило интерпретации. Во втором случае соответствие между сообщением и информацией возможно в двух вариантах: 1) одна и та же информация может передаваться различными сообщениями (в частности, новости могут быть получены по радио, из газеты, по телефону и пр.); 2) одно и то же сообщение может содержать различную информацию для разных приемников (скажем, падение курса акций на бирже для одних катастрофа, а для других – возможность обогащения).

Поскольку последовательность сигналов есть сообщение, качество прерывности-непрерывности сигналов переносится и на сообщение. Существуют такие понятия, как непрерывное (аналоговое), дискретное, квантованное и цифровое сообщение. Заметим, что информация данным качеством не обладает, так как информация – категория нематериальная и не может обладать свойством дискретности или непрерывности. Хотя одна и та же информация может быть представлена посредством различных сообщений, в том числе и отличающихся характером сигналов. В информатике иногда используются словосочетания "непрерывная информация" и "дискретная информация". Они являются результатом сокращения таких терминов, как информация, представленная посредством непрерывных сигналов, и информация, представленная посредством дискретных сигналов. Поэтому, когда речь идет о видах информации, правильнее говорить о формах ее представления в сообщении или о видах сообщений.

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

Знак, буква и символ

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

Набор знаков, в котором установлен порядок их следования, называется алфавитом. Алфавит – это упорядоченная совокупность знаков. Порядок следования знаков в алфавите называется лексикографическим и предоставляет возможность устанавливать отношения "больше – меньше": для двух знаков Г < Д, если порядковый номер у Г в алфавите меньше, чем у Д.

Знаки, используемые для обозначения фонем в устной речи, называются буквами, а их совокупность – алфавитом языка.

Сами по себе знак или буква не несут никакого смыслового содержания. Однако такое содержание им может быть приписано, в этом случае знак будет называться символом.

Например, электрическое напряжение в физике принято обозначать буквой U, и, следовательно, U в формулах является символом физической величины "электрическое напряжение". Другим примером символов могут служить пиктограммы, обозначающие в компьютерных программах объекты или действия.

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

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