Нехай а ане подобаються уроки. Контрольна робота з інформатики та ікт "елементи алгебри логіки". Завдання для індивідуальної роботи

Мета уроку:

освітні

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

Розвиваючі

Розвиток пізнавальної діяльності.
Розвиток вміння аналізувати, робити узагальнюючі висновки.

виховні

Розуміння зв'язків між іншими учнями, культурою поведінки.

ЦОР: Презентації "Історія логіки" [додаток 1], "Форми мислення" [додаток 2].

План уроку:

Організаційний момент.
Що вивчає логіка? Якими основними поняттями оперує логіка?
Звідки сталася алгебра висловлювань? Повідомлення учня.
Як виходять складні висловлювання? Логічні операції.
Готуємося до ЄДІ. Закріплення знань.

ХІД УРОКУ

I. Організаційний момент.

Постановка проблеми:

Що спільного у алгебри з алгеброю логіки?
Які операції є в алгебрі логіки і як вони позначаються?
Що буде результатом операції?
Які логічні операції ми використовуємо при формулюванні теорем?

II. Актуалізація.

Фронтальне опитування "Що таке логіка? Основні поняття логіки ".

Питання для повторення:

Що вивчає логіка? Якими основними поняттями оперує логіка?

Що таке "поняття" з точки зору логіки? Наведіть приклади.

Які дві сторони можна виділити в понятті?

Що таке висловлювання? Які види висловлювань Ви знаєте (Привести приклади загальних, приватних і одиничних висловлювань)

З даних пропозицій виберіть ті, які є висловлюваннями, і обґрунтуйте свій вибір.

Наполеон був французьким імператором.
Чому дорівнює відстань від Землі до Марса?
Увага! Подивіться направо.
Електрон - елементарна частинка.
Не порушуйте правил дорожнього руху!
Полярна зірка знаходиться в сузір'ї малої ведмедиці.
Не все те золото що блищить.

Поясніть, чому формулювання будь-теореми є висловлюванням.

Які з наведених прикладів є приватними висловлюваннями, а які загальними?

Не всі книги містять корисну інформацію.
Кішка є домашнім тваринам.
Деякі учні двієчники.
Всі ананаси приємні на смак.
Багато рослин мають цілющі властивості.
Будь-нерозумна людина ходить на руках.
А - перша буква в алфавіті.

За допомогою чого виводяться нові знання про предмети?

Якого виду умовиводи ви знаєте?

Наведіть приклади дедуктивних, індуктивних умовиводів і по аналогії.

III. Формування нових знань.

Невелике повідомлення учня про те, як і коли виникла алгебра висловлювань.

Можна використовувати презентацію "Історія логіки" [додаток 1].

Учитель. Дослідження в алгебрі логіки тісно пов'язані з вивченням висловлювань. За допомогою висловлювань ми встановлюємо властивості, взаємозв'язки з об'єктами. Висловлення істинно, якщо воно адекватно відображає цей зв'язок, в іншому випадку воно помилкове.

Визначення. Висловлення називається простим, якщо ніяка його частина не є висловлюванням.

Терміни, що вживаються в звичайній мові зв'язки "і", "або", "не", "якщо ..., то ...", "тоді і тільки тоді, коли ..." і т.п. дозволяють з вже заданих висловлювань будувати нові складні висловлювання. Це і є логічні операції, подібно додаванню, множенню в звичайній алгебрі.

Істинність або хибність отриманих таким чином висловлювань залежить від істинності чи хибності вихідних висловлювань і відповідного трактування в'язок як логічних операцій над висловлюваннями.

Для позначення істинності, як правило, використовуються знаки "І" та "1", а для позначення помилковості - символи "Л" і "0".

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

Розглянемо логічні операції.

1. Кон'юнкція.

Визначення. Висловлювання, складене з двох і більше висловлювань шляхом об'єднання їх зв'язкою "І", називається кон'юнкція або логічним множенням.

Тут можна поміркувати з хлопцями, взявши в якості простих висловлювань очевидні А \u003d (2 * 2 \u003d 4) і В \u003d (2 * 2 \u003d 5) і ін. Робимо висновок:

Висловлюючи кон'юнкцію, ми стверджуємо, що виконуються обидві ці події, про які йде мова.

Наприклад, повідомляючи (Петрови поїхали на дачу і взяли з собою собаку) ми висловлюємо в одному висловлюванні своє переконання, що відбулися обидві ці події.

Формулюємо правило.

Правило. Складене висловлювання, утворене з помощьюкон'юнкціі, істинно тоді і тільки тоді, коли істинні всі вхідні в нього прості висловлювання.

Позначення. АВ, А & В, А * В, А and В.

Таблиця істинності.

Завдання. Наведіть приклади кон'юнкції.

Приклад. Розглянемо два висловлювання А \u003d (Завтра буде мороз), і В \u003d (Завтра буде йти сніг). Нове висловлювання А & В істинно лише в разі, коли будуть істинні обидва цих висловлювання.

У російській мові кон'юнкції також відповідають, крім союзу "і", зв'язки "а" і "але".

2. Диз'юнкція.

Визначення. Висловлювання, складене з двох і більше висловлювань шляхом об'єднання їх зв'язкою "АБО", називається диз'юнкція або логічним складанням.

Аналогічно, розмірковуємо на предмет істинності складного висловлювання, побудованого за допомогою "або" на прикладах, очевидних для хлопців.

Формулюємо висновок:

У висловлюваннях, що містять в'язку "АБО", вказується на існування двох або декількох можливих подій, з яких хоча б одне повинно бути здійснено.

Наприклад, повідомляючи (Толя п'є чай або читає книгу) ми висловлюємо в одному висловлюванні своє переконання, що сталося хоча б одне з цих подій.

Формулюємо правило.

Правило. Складене висловлювання, утворене за допомогою диз'юнкції, істинно тоді, коли істинно хоча б одне, що входять в нього простих висловлювання.

Позначення. АВ, А + В, А or В.

Таблиця істинності.

Завдання. Наведіть приклади.

Приклад. Нехай А \u003d (Колумб був в Індії), і В \u003d (Колумб був в Єгипті).

Висловлення АВ було це слово як в разі, якщо Колумб був в Індії, але не був в Єгипті, так і в разі, якщо він був в Єгипті, але не був в Індії. Але цей вислів буде помилково, тому що він не був ні в Індії, ні в Єгипті.

3. Що виключає "АБО".

Союз "або" може застосовуватися в мові і в іншому, яка виключає сенсі. Тоді він відповідає іншому висловом - розділової або суворої диз'юнкції.

Визначення. Висловлювання, складене з двох і більше висловлювань шляхом об'єднання їх зв'язкою "АБО", називається розділової диз'юнкція (суворої), що виключає "або", складанням по модулю 2.

На відміну від звичайної диз'юнкції ми стверджуємо, що відбудеться одна подія з двох.

Наприклад, (Толя п'є чай або молоко), (Коля сидить на трибуні А чи на трибуні Б).

Формулюємо правило.

Правило. Сувора або розділова диз'юнкція - логічна операція, яка ставить у відповідність ці два вислови нове висловлювання, яке є істинним тоді і тільки тоді, коли рівно одне з висловлювань істинно .

Позначення. АВ.

Таблиця істинності.

Завдання. Наведіть приклади.

Приклад. Нехай А \u003d (Кішка полює за мишами), В \u003d (Кішка спить на дивані). Нове висловлювання АВ буде істинні в двох випадках, коли кішка полює за мишами або коли кішка мирно спить. Це висловлювання буде хибним, якщо кішка не робить ні того, ні іншого, так само як і в разі, коли передбачається, що обидві події будуть відбуватися одночасно.

4. Інверсія.

Визначення. Заперечення (інверсія) - логічна операція, яка кожному елементарному висловом ставить у відповідність нове висловлювання, значення якого протилежно вихідному.

У російській мові для побудови заперечення використовується зв'язка "невірно, що".

Питання: Коли ж нове висловлювання, побудоване таким чином, буде істинним?

Інверсія звертає справжнє висловлювання в помилкове, а помилкове в справжнє.

Завдання. Наведіть приклади.

Приклад. Запереченням висловлювання (У мене вдома є комп'ютер) буде висловлювання (Невірно, що у мене вдома є комп'ютер) або, що те ж саме (У мене вдома немає комп'ютера).

Позначення. ¬А

Таблиця істинності.

1. Запереченням висловлювання (Я не знаю татарської мови) буде висловлювання (Невірно, що я не знаю татарської мови) або (Я знаю татарську мову).

2. Запереченням висловлювання (Всі юнаки 11-х класів - відмінники) є висловлювання (Невірно, що всі юнаки 11-х класів - відмінники) або (Не всі юнаки 11-х класів - відмінники) або іншими словами, (Деякі юнаки 11- х класів - НЕ відмінники).

На перший погляд здається, що побудувати заперечення до заданого висловом досить просто. Однак це не так.

Приклад 1. Висловлення (Всі юнаки 11-х класів - НЕ відмінники) не є запереченням висловлювання (Всі юнаки 11-х класів - відмінники). Пояснюється це наступним чином. Висловлювання (Всі юнаки 11-х класів - відмінники) помилково. Запереченням до помилкового висловлення повинно бути висловлювання, що є істинним. Але висловлювання (Всі юнаки 11-х класах не відмінники) не є істинним, так як серед одинадцятикласників є як відмінники, так і не відмінники.

Приклад 2. Для висловлювання (На стоянці стоять червоні "Жигулі") наступні пропозиції запереченнями є не будуть:

1) (На стоянці коштують не червоні "Жигулі");

2) (На стоянці стоїть білий "Мерседес");

З) (Червоні "Жигулі" коштують не на стоянці).

Розібратися в цьому прикладі пропонується самостійно. Клас ділиться на групи, всередині групи обговорюється цей приклад, потім спікери висловлюють свою думку від імені групи.

Проаналізувавши наведені приклади, можна вивести корисне правило.

Правило побудови заперечення до простого висловом:

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

Завдання. Побудуйте заперечення для висловлювань:

Всі хлопці вміють плавати.
Неможливо створити вічний двигун.
Кожна людина - художник.
Людина все може.
Сьогодні в театрі йде опера "Євгеній Онєгін".

5. Пріоритет операцій.

Кожне складене висловлювання можна виразити у вигляді формули (логічного виразу), до якої увійдуть символи, що позначають висловлювання і їх заперечення, з'єднані знаками логічних операцій.

Старшинство операцій:

інверсія
кон'юнкція
диз'юнкція

Завдання. Розставити порядок дій логічного виразу

IV. Закріплення вивченого.

Наступні завдання виконуються самостійно, потім йде обговорення рішення.

Завдання для учнів:

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

а) Число 376 парне і тризначне.

б) Взимку діти катаються на ковзанах або на лижах.

в) Новий рік ми зустрінемо на дачі або на Красній площі.

г) Невірно, що Сонце рухається навколо Землі.

е) Земля має форму кулі, який з космосу здається блакитним.

ж) На уроці математики старшокласники відповідали на запитання вчителя, а також писали самостійну роботу.

3. Чи є запереченнями один одного наступні пари пропозицій? Обговорення.

а) Він - мій друг. Він - мій ворог.

б) Великий будинок. Невеликий дім.

в) Великий будинок. Маленький дім.

г) Х\u003e 2. Х< 2.

4. Нехай р \u003d (Ані подобаються уроки математики), а q \u003d (Ані подобаються уроки хімії). Висловіть наступні формули на природній мові. Коментування.

картки

а й (Марс - планета) - справжнє висловлювання;
b і (Марс - планета) - хибне висловлювання;
c або (Сонце - супутник Землі) - справжнє висловлювання;
d або (Сонце - супутник Землі) - хибне висловлювання.

Визначте значення логічних змінних a, b, c, d, якщо:

а чи (1 літр молока дорожче 1 кг вершкового масла) - це правда,
b і (1 літр молока дорожче 1 кг вершкового масла) - помилково;
c або (масло дорожче сиру) - це правда,
d і (масло дорожче сиру) - хибне висловлювання.

Нехай а \u003d "ця ніч зоряна", а b \u003d "ця ніч холодна". Висловіть наступні формули звичайною мовою:

а й b;
а й не b;
нЕ а й не b;

Додаткове завдання - завдання з ЄДІ.

Завдання з ЄДІ

А10. При яких значеннях змінних логічне вадання. Розставити порядок дій логічного вираженія.еского вираження), до якої увійдуть символи, що позначають висказиванираженіе

¬ (М \u003d N) v ¬ (М<Р) принимает значение “Ложь”?

M \u003d 1; N \u003d 1; P \u003d 0
M \u003d -1; N \u003d -1; P \u003d 0
M \u003d 1; N \u003d 1; P \u003d 0
M \u003d 0; N \u003d 0; P \u003d -1

А12. З двох висловлювань "дядько Федір і кіт матросках не люблять Молоко" і "Кіт Матроскін не любить" Молоко одне хибно, а інше істинно. Хто з них не любить молоко?

1) Обидва не люблять молоко.

2) Обидва люблять Молоко.

З) Кіт Матроскін любить Молоко, а дядько Федір немає.

4) дядько Федір любить молоко, а Кіт Матроскін - немає.

V. Домашнє завдання.

Підручник: Угриновича, 10-11 кл., П.3.2 (с.125-129), упр. 3.1.

Придумати приклади для кожної логічної операції.

VI. Підсумки уроку.

Питання для підбиття підсумку уроку:

Що нового ви дізналися сьогодні на уроці?
Як ми можемо отримати складні висловлювання з декількох простих?
Які логічні операції ви тепер знаєте?
Чому залежить істинність складного висловлювання?

література

Математичні основи інформатики. Елективний курс: навчальний посібник / Андрєєва Є.В., Босова Л.Л., Фаліна І.М. М .: БИНОМ. Лабораторія знань, 2005.
Інформатика. Задачник-практикум в 2 т. / Під ред. Семакіна І.Г., Хеннера Є.К. М.: Лабораторія базових знань, 2001..
Готуємося до ЄДІ з інформатики. Елективний курс: навчальний посібник / Н.Н.Самилкіна, С.В. Русаков, А.П. Шестаков, С.В. Баданіна. - М .: БИНОМ. Лабораторія Знання, 2008.

5.1. Встановіть, які з наступних пропозицій є логічними висловлюваннями, а які - ні (поясніть чому):

- а) "Сонце є супутник Землі";
- б) "2+3 =4 ";
- в) "сьогодні чудова погода";
- г) "в романі Л.Н. Толстого "Війна і світ" 3 432 536 слів";
- д) "Санкт-Петербург розташований на Неві";
- е) "музика Баха занадто складна";
- ж) "перша космічна швидкість дорівнює 7.8 км / сек";
- з) "залізо - метал";
- і) "якщо один кут в трикутнику прямий, то трикутник буде тупоугольние";
- к) "якщо сума квадратів двох сторін трикутника дорівнює квадрату третьої, то він прямокутний".

[ відповідь ] 5.1. є висловлюваннями: А), г), д), ж), з), і), к);
не є висловлюваннями: Б); в); е).

5.2. Вкажіть, які з висловлювань попередньої вправи істинні, які - хибні, а які відносяться до числа тих, істинність яких важко або неможливо встановити.
[ відповідь ] 5.2. справжні: д), з), к);
помилкові: а), і);
істинність важко встановити: Г);
можна розглядати і як справжнє, і як помилкове в залежності від необхідної точності уявлення: ж).

5.3. Наведіть приклади істинних і хибних висловлювань:

- а) з арифметики; б) з фізики;
- в) з біології; г) з інформатики;
- д) з геометрії; е) з життя.

[ відповідь ] 5.3. Зразки.
Істинні висловлювання: а) "2+2=4 "; б) "Сила тяжіння тіл обернено пропорційна квадрату відстані між ними" в) "Зайці харчуються рослинами"; г) "Біт - фундаментальна одиниця інформації, яка використовується в теорії інформації"; д) "Два трикутники рівні, якщо дві сторони і кут між ними одного трикутника дорівнюють двом сторонам і куту між ними іншого трикутника"; е) "Понеділок - перший день тижня".
помилкові висловлювання: а) "4+3=5" ; б) "Тіло падає на Землю з прискоренням, пропорційним своїй масі"; в) "Тварини це нежива природа" г) "Інформатика - наука про термічній обробці металів"; д) "Квадрат це фігура у якій п'ять сторін"; е) "Лев - домашня тварина"

5.4. Сформулюйте заперечення наступних висловлювань або висказивательной форм:

- а) "Ельбрус - найвища гірська вершина Європи";
- б) "2>=5 ";
- в) "10<7 ";
- г) "всі натуральні числа цілі";
- д) "через будь-які три точки на площині можна провести окружність";
- е) "тенісист Кафельников не програв фінальну гру";
- ж) "";
- з) "цього ранку ясна і тепле";
- і) "число n ділиться на 2 або на 3";
- к) "";
- л) "на контрольній роботі кожен учень писав своєю ручкою".

[ відповідь ] 5.4. а) "Ельбрус - НЕ найвища гірська вершина Європи"; б) "2<5" ; в) "10>=7" ; г) "Не всі натуральні числа цілі"; д) «Не через будь-які три точки на площині можна провести окружність"; е) "Тенісист Кафельников програв фінальну гру"; ж) "Мішень не уражена першим пострілом"; з) "Цього ранку не ясне або воно не тепле" (Пояснення. Нехай А = "Цього ранку ясна", а B = "Цього ранку тепле". тоді "Цього ранку ясна і тепле" можна записати як А. В, запереченням чого є, що відповідає висказивательной формі "Цього ранку не ясне або воно не не теплий"; і)"Число n не ділиться на 2 і воно ділиться на 3"; к) "Цей трикутник НЕ рівнобедрений або він не прямокутний"; л) "Не кожен учень писав контрольну своєю ручкою" (різновид: "Хтось писав контрольну не своєю ручкою").

5.5. Визначте, які з висловлювань (висказивательной форм) в наступних парах є запереченнями один одного, а які ні:

- а) "5<10 ", "5>10 ";
- б) "10>9 ", "10<=9 ";
- в) "мішень вражена першим пострілом", "мішень вражена другим пострілом";
- г) "машина зупинялася у кожного з двох світлофорів", "машина не зупинялася у кожного з двох світлофорів",
- д) "людству відомі всі планети Сонячної системи", "в Сонячній системі є планети, невідомі людству";
- е) "існують білі слони", "всі слони сірі";
- ж) "кит - ссавець", "кит - риба";
- з) "невірно, що точка А не лежить на прямій а", "точка А лежить на прямій а";
- і) "пряма а паралельна прямій b", "пряма a перпендикулярна прямий b";
- к) "цей трикутник рівнобедрений і прямокутний", "цей трикутник НЕ рівнобедрений або він не прямокутний".

[ відповідь ] 5.5. Є запереченнями один одного: б), г), д), к);
не є запереченнями один одного: а), в), е), ж), з), і).

5.6. Визначте значення істинності висловлювань:

- а) "наявності атестата про повну загальну середню освіту досить для вступу до інституту";
- б) "наявність атестата про повну загальну середню освіту необхідно для вступу до інституту";
- в) "якщо ціле число ділиться на 6, то воно ділиться на 3";
- г) "подобу трикутників є необхідною умовою їх рівності";
- д) "подобу трикутників є необхідною і достатньою умовою їх рівності";
- е) "трикутники подібні тільки в разі їх рівності";
- ж) "трикутники рівні тільки в разі їх подібності";
- з) "рівність трикутників є достатньою умовою їх подібності";
- і) "для того, щоб трикутники були нерівні, досить, щоб вони були неподібні";
- к) "для того, щоб чотирикутник був квадратом, досить, щоб його діагоналі були рівні і перпендикулярні".

[ відповідь ] 5.6. Правдиві: б), в), г), з), к), і);
помилкові: а), д), е), ж).

5.7. Підставте в наведені нижче висказивательной форми замість логічних змінних a, b, c, d такі висловлювання, щоб отримані таким чином складові висловлювання мали сенс в повсякденному житті:

- а) якщо (а або (b і з)), то d;
- б) якщо (нЕ а і нЕ b), то (з або d);
- в) (а або b) тоді і тільки тоді, коли (з і не d).

5.8. Формалізує наступний висновок: "Якщо a і b істинні, то c - істинно. але c - помилково: значить, a або b помилкові ".
[ відповідь ] 5.8. .

Число 376 парне і тризначне.

Число ділиться на 3 тоді і тільки тоді, коли сума цифр числа ділиться на 3

символом F x , y , z F F ? 1)

Самостійна робота

Варіант 2

нехай P Q

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

Взимку діти катаються на ковзанах або на лижах.
Якщо сума цифр натурального числа ділиться на 3, то число ділиться на 3.

символом F позначено одну з таких логічних виразів від трьох аргументів:x , y , z . Дан фрагмент таблиці істинності вираженняF . Який вираз відповідаєF ? 1)

Самостійна робота

варіант 3

нехай P \u003d (Ані подобаються уроки математики), аQ \u003d (Ані подобаються уроки хімії). Висловіть наступні формули природною мовою:

Невірно, що сонце рухається навколо Землі.
Якщо вчора була неділя, то Діма вчора не був у школі і весь день гуляв.

Самостійна робота

варіант 4

На уроці математики старшокласники відповідали на запитання вчителя, а також писали самостійну роботу.

Ключові слова:

алгебра логіки
вислів
логічна операція
кон'юнкція
диз'юнкція
заперечення
логічне вираз
таблиця істинності
закони логіки

1.3.1. висловлювання

Алгебра в широкому сенсі цього слова - наука про загальні операціях, аналогічних додаванню і множенню, які можуть виконуватися над різноманітними математичними об'єктами. Багато математичні об'єкти (цілі і раціональні числа, многочлени, вектори, безлічі) ви вивчаєте в шкільному курсі алгебри, де знайомитеся з такими розділами математики, як алгебра чисел, алгебра многочленів, алгебра множин і т. Д.

Для інформатики важливий розділ математики, званий алгеброю логіки; об'єктами алгебри логіки є висловлювання.

Наприклад, щодо пропозицій «Великий російський вчений М. В. Ломоносов народився в 1711 році» та «Two plus six Is eight» можна однозначно сказати, що вони істинні. Пропозиція «Взимку горобці впадають в сплячку» помилково. Отже, ці пропозиції є висловлюваннями.

Наприклад, пропозиція «Ця пропозиція є хибним» не є висловлюванням, так як щодо нього не можна сказати, істинно воно або помилково, без того, щоб не отримати протиріччя. Дійсно, якщо прийняти, що пропозиція істинно, то це суперечить сказаному. Якщо ж прийняти, що пропозиція помилково, то це означає, що воно істинне.

Щодо пропозиції «Комп'ютерна графіка - найцікавіша тема в курсі шкільної інформатики» також не можна однозначно сказати, істинно воно або помилково. Подумайте самі чому.

Наприклад, не є висловлюваннями такі пропозиції, як: «Запишіть домашнє завдання», «Як пройти в бібліотеку?», «Хто до нас прийшов? ».

Прикладами висловлювань можуть служити:

«Na - метал» (справжнє висловлювання);
«Другий закон Ньютона виражається формулою F \u003d m а» (справжнє висловлювання);
«Периметр прямокутника з довжинами сторін a u b дорівнює а b» (хибне висловлювання).

Чи не є висловлюваннями числові вирази, але з двох числових виразів можна скласти висловлювання, з'єднавши їх знаками рівності або нерівності. наприклад:

«34-5 \u003d 2 4» (справжнє висловлювання);
«II4-VI\u003e VIII» (хибне висловлювання).

Чи не є висловлюваннями і рівності або нерівності, що містять змінні. Наприклад, пропозиція «X< 12» становится высказыванием только при замене переменной каким-либо конкретным значением: «5 < 12» - истинное высказывание; «12 < 12» - ложное высказывание.

Обгрунтування істинність або хибність висловлювань вирішується тими науками, до сфери яких вони відносяться. Алгебра логіки відволікається від смислової змістовності висловлювань. Її цікавить тільки те, істинно або хибно це висловлювання. В алгебрі логіки висловлювання позначають буквами і називають логічними змінними. При цьому якщо висловлювання істинно, то значення відповідної йому логічної змінної позначають одиницею (А \u003d 1), а якщо помилково - нулем (Б \u003d 0). 0 і 1, що позначають значення логічних змінних, називаються логічними значеннями.

Оперуючи логічними змінними, які можуть бути рівні тільки 0 або 1, алгебра логіки дозволяє звести обробку інформації до операцій з двійковими даними. Саме апарат алгебри логіки покладено в основу комп'ютерних пристроїв зберігання і обробки інформації. Із застосуванням елементів алгебри логіки ви будете зустрічатися і в багатьох інших розділах інформатики.

1.3.2. Логічні операції

Висловлювання бувають прості і складні. Висловлення називається простим, якщо ніяка його частина сама не є висловлюванням. Складні (складові) висловлювання будуються з простих за допомогою логічних операцій.

Розглянемо основні логічні операції, певні над висловлюваннями. Всі вони відповідають зв'язкам, вживаним в природній мові.

кон'юнкція

Розглянемо два висловлювання: А \u003d «Основоположником алгебри логіки є Джордж Буль», В \u003d «Дослідження Клода Шеннона дозволили застосувати алгебру логіки в обчислювальній техніці». Очевидно, нове висловлювання «Основоположником алгебри логіки є Джордж Буль, і дослідження Клода Шеннона дозволили застосувати алгебру логіки в обчислювальній техніці» істинно тільки в тому випадку, коли одночасно істинними обидва вихідних висловлювання.

Для запису кон'юнкції використовуються наступні знаки:,, І, &. Наприклад: А В, А В, А І В, А & Б.

Кон'юнкцію можна описати у вигляді таблиці, яку називають таблицею істинності:

У таблиці істинності перераховуються всі можливі значення вихідних висловлювань (стовпці А і В), причому відповідні їм виконавчі числа, як правило, мають у своєму розпорядженні в порядку зростання: 00, 01, 10, 11. В останньому стовпчику записано результат виконання логічної операції для відповідних операндів.

Інакше кон'юнкцію називають логічним множенням. Подумайте чому.

диз'юнкція

Розглянемо два висловлювання: А \u003d «Ідея використання в логіці математичної символіки належить Готфрід Вільгельм Лейбніц», В \u003d «Лейбніц є основоположником бінарної арифметики». Очевидно, нове висловлювання «Ідея використання в логіці математичної символіки належить Готфрід Вільгельм Лейбніц або Лейбніц є основоположником бінарної арифметики» помилково тільки в тому випадку, коли одночасно помилкові обидва вихідних висловлювання.

Самостійно встановіть істинність або хибність трьох розглянутих висловлювань.

Для запису диз'юнкції використовуються наступні знаки: v, |, АБО, +. Наприклад: AvB, А | В, А ЧИ Б, А + Б.

Диз'юнкція визначається наступною таблицею істинності:

Інакше диз'юнкцію називають логічним складанням. Подумайте чому.

інверсія

Для запису інверсії використовуються наступні знаки: НЕ, ¬, ~. Наприклад: НЕ, ¬, ~.

Інверсія визначається наступною таблицею істинності:

Інверсію інакше називають логічним запереченням.

Запереченням висловлювання «У мене вдома є комп'ютер» буде висловлювання «Невірно, що у мене вдома є комп'ютер» або, що в російській мові те ж саме, «У мене вдома немає комп'ютера». Запереченням висловлювання «Я не знаю китайську мову» буде висловлювання «Невірно, що я не знаю китайську мову» або, що в російській мові один і той же, «Я знаю китайську мову». Запереченням висловлювання «Все юнаки 9-х класів - відмінники» є вислів «Невірно, що всі юнаки 9-х класів - відмінники», іншими словами, «Не всі юнаки 9-х класів - відмінники».

Таким чином, при побудові заперечення до простого висловом або використовується мовний зворот «невірно, що ...», або заперечення будується до сказуемому, тоді до відповідного дієслова додається частка «не».

Будь-яке складне висловлювання можна записати у вигляді логічного виразу - вираження, що містить логічні змінні, знаки логічних операцій і дужки. Логічні операції в логічному вираженні виконуються в такому порядку: інверсія, кон'юнкція, диз'юнкція. Змінити порядок виконання операцій можна за допомогою розміщення дужок.

приклад 1. Нехай А \u003d «На Web-сторінці зустрічається слово" крейсер "», В \u003d «На Web-сторінці зустрічається слово" лінкор "». Розглядається деякий сегмент мережі Інтернет, що містить 5 000 000 Web-сторінок. У ньому висловлювання А істинно для 4800 сторінок, висловлювання В - для 4500 сторінок із, а висловлювання A v В - для 7000 сторінок. Для якої кількості Web-сторінок в цьому випадку будуть істинними такі вирази і висловлювання?

а) НЕ (А ЧИ В);

в) На Web-сторінці зустрічається слово "крейсер" і не зустрічається слово "лінкор".

Рішення. Зобразимо безліч всіх Web-сторінок даного сектора мережі Інтернет кругом, всередині якого розмістимо два кола: одному з них відповідає безліч Web-сторінок, де істинно висловлювання А, другого - де істинно висловлювання В (рис. 1.3).

Мал. 1.3.
Графічне зображення множин Web-сторінок

Зобразимо графічно безлічі Web-сторінок, для яких істинні вирази і висловлювання а) - в) (рис. 1.4)

Мал. 1.4.
Графічне зображення множин Web-сторінок, для яких істинні вирази і висловлювання а) - в)

Побудовані схеми допоможуть нам відповісти на питання, що містяться в завданні.

Вираз А ЧИ В істинно для 7000 Web-сторінок, а всього сторінок 5 000 000. Отже, вираз А ЧИ В хибно для 4 993 000 Web-сторінок. Інакше кажучи, для 4 993 000 Web-сторінок істинно вираз НЕ (А ЧИ В).

Вираз A v B істинно для тих Web-сторінок, де істинно А (4800), а також тих Web-сторінок, де істинно В (4500). Якби все Web-сторінки були різні, то вираз A v В було б істинно для 9300 (4800 + 4500) Web-сторінок. Але, згідно з умовою, таких Web-сторінок за все 7000. Це означає, що на 2300 (9300 - 7000) Web-сторінках зустрічаються обидва слова одночасно. Отже, вираз А & В істинно для 2300 Web-сторінок.

Щоб з'ясувати, для скількох Web-сторінок істинно висловлювання А і одночасно помилково висловлювання В, випливає з 4800 відняти 2300. Таким чином, висловлювання «На Web-сторінці зустрічається слово" крейсер "І не зустрічається слово" лінкор "» істинно на 2500 Web- сторінках.

Самостійно запишіть логічне вираз, що відповідає розглянутому висловом.

На сайті Федерального центру інформаційно-освітніх ресурсів (http://fcoir.edu.ru/) розміщений інформаційний модуль «Висловлення. Прості і складні висловлювання. Основні логічні операції ». Знайомство з цим ресурсом дозволить вам розширити уявлення з досліджуваної теми.

1.3.3. Побудова таблиць істинності для логічних виразів

Для логічного виразу можна побудувати таблицю істинності, яка ніколи, які значення приймає вираз при всіх наборах значень назв змінних. Для побудови таблиці істинності слід:

підрахувати n - число змінних у виразі;
підрахувати загальну кількість логічних операцій в вираженні;
встановити послідовність виконання логічних операцій з урахуванням дужок і пріоритетів;
визначити число стовпців в таблиці: число змінних + число операцій;
заповнити шапку таблиці, включивши в неї змінні і операції відповідно до послідовності, встановленої в п. 3;
визначити число рядків в таблиці (не рахуючи шапки таблиці) m \u003d 2n;
виписати набори вхідних змінних з урахуванням того, що вони представляють собою цілий ряд n-розрядних двійкових чисел від 0 до 2 n - 1;
провести заповнення таблиці по стовпцях, виконуючи логічні операції відповідно до встановленої послідовністю.

Побудуємо таблицю істинності для логічного виразу A v А & В. В ньому дві змінні, дві операції, причому спочатку виконується кон'юнкція, а потім - диз'юнкція. Всього в таблиці буде чотири стовпці:

Набори вхідних змінних - це цілі числа від Про до 3, представлені в двухразрядного двійковому коді: 00, 01, 10, 11. Заповнена таблиця істинності має вигляд:

Зверніть увагу, що останній рядок (результат) збігся зі стовпцем А. В такому випадку кажуть, що логічне вираз A v А & Б рівносильно логічного виразу А.

1.3.4. Властивості логічних операцій

Розглянемо основні властивості (закони) алгебри логіки.

Закони алгебри логіки можуть бути доведені за допомогою таблиць істинності.

Доведемо розподільний закон для логіческіческого складання:

A v (В & С) \u003d (А V В) & (A v С).

Збіг стовпців, відповідних логічним виразами в лівій і правій частинах рівності, доводить справедливість розподільного закону для логічного складання.

приклад 2. Знайдемо значення логічного виразу для числа Х \u003d 0.

Рішення. При X \u003d 0 отримуємо наступне логічне вираз:. Так як логічні вирази 0< 3, 0 < 2 истинны, то, подставив их значения в логическое выражение, получаем: 1&Т = 1&0 = 0.

1.3.5. Рішення логічних задач

Розглянемо кілька способів вирішення логічних завдань.

завдання 1. Коля, Вася і Сергій гостювали влітку у бабусі. Одного разу один з хлопчиків ненароком розбив улюблену бабусину вазу. На питання, хто розбив вазу, вони дали такі відповіді:

Сергій: 1) Я не розбивав. 2) Вася не розбивав.

Вася: 3) Сергій не розбивати. 4) Вазу розбив Коля.

Коля: 5) Я не розбивав. 6) Вазу розбив Сергій.

Бабуся знала, що один з її онуків, назвемо його правдивим, обидва рази сказав правду; другий, назвемо його жартівником, обидва рази сказав неправду; третій, назвемо його хитруном, один раз сказав правду, а інший раз - неправду. Назвіть імена правдивого, жартівника і хитруна. Хто з онуків розбив вазу?

Рішення. Нехай К \u003d «Коля розбив вазу», В \u003d «Вася розбив вазу», С \u003d «Серьожа розбив вазу». Складемо таблицю істинності, з якої представимо висловлювання кожного хлопчика 1.

1 З урахуванням того, що ваза розбита одним онуком, можна було складати не всю таблицю, а тільки її фрагмент, що містить следуюнще набори вхідних змінних: 001, 010, 100.

Виходячи з того, що знає про онуків бабуся, слід шукати в таблиці рядки, що містять в будь-якому порядку три комбінації значень: 00, 11, 01 (або 10). Таких рядків в таблиці виявилося дві (вони відзначені галочками). Згідно з другою з них, вазу розбили Коля і Вася, що суперечить умові. Відповідно до першої з знайдених рядків, вазу розбив Сергію, він же виявився хитруном. Жартівником виявився Вася. Ім'я правдивого онука - Коля.

завдання 2. У змаганнях з гімнастики беруть участь Алла, Валя, Сима і Даша. Вболівальники висловили припущення про можливих переможців:

Сима буде першою, Валя - другий;
Сима буде другий, Даша - третій;
Алла буде другий, Даша - четвертою.

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

Рішення. Розглянемо прості висловлювання:

C 1 \u003d «Сіма посіла перше місце»;

В 2 \u003d «Валя посіла друге місце»;

З 2 \u003d «Сіма посіла друге місце»;

Д 3 \u003d «Даша посіла третє місце»;

А 2 \u003d «Алла посіла друге місце»;

Д 4 \u003d «Даша посіла четверте місце».

Так як в кожному з трьох припущень одне з висловлювань істинно, а інше брехливо, то можна зробити висновок наступне:

C 1 + В 2 \u003d 1, С 1 В 2 \u003d 0;
З 2 + Д 3 \u003d 1, С 2 Д 3 \u003d 0;
А 2 + Д 4 \u003d 1, А 2 Д 4 \u003d 0.

Логічне твір справжніх висловлювань буде істинним:

(З 1 + В 2) (С 2 + Д 3) (А 2 + Д 4) \u003d 1.

На підставі розподільного закону перетворимо ліву частину цього виразу:

(З 1 З 2 + С 1 Д 3 + В 2 С 2 + В 2 Д 3) (А 2 + Д 4) \u003d 1.

Висловлювання З 1 З 2 означає, що Сима зайняла і перше, і друге місця. Згідно з умовою задачі, це висловлення помилкове. Помилковим є і висловлювання В 2 С 2. З огляду на закон операцій з константою 0, запишемо:

(З 1 Д 3 + В 2 Д 3) (А 2 + Д 4) \u003d 1.

Подальше перетворення лівій частині цієї рівності і виключення завідомо неправдивих висловлювань дають:

З 1 Д 3 А 2 + С 1 Д 3 Д 4 + В 2 Д 3 А 2 + В 2 Д 3 Д 4 \u003d 1.

C 1 Д 3 А 2 \u003d 1.

З останнього рівності випливає, що С 1 \u003d 1, Д 3 \u003d 1, А 2 \u003d 1. Це означає, що Сима посіла перше місце, Алла - друга, Даша - третє. Отже, Валя посіла четверте місце.

Познайомитися з іншими способами вирішення логічних завдань, а також взяти участь в Інтернет-олімпіадах і конкурсах по їх вирішенню ви зможете на сайті «Математика для школярів» (http://www.kenqyry.com/).

На сайті http://www.kaser.com/ ви зможете скачати демонстраційну версію дуже корисною, розвиваючої логіку і вміння міркувати логічної головоломки Шерлок.

1.3.6. Логічні елементи

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

Ви вже знаєте, що будь-яка інформація може бути представлена \u200b\u200bв дискретної формі - у вигляді фіксованого набору окремих значень. Пристрої, які обробляють такі значення (сигнали), називаються дискретними. Дискретний перетворювач, який видає після обробки двійкових сигналів значення однієї з логічних операцій, називається логічним елементом.

На рис. 1.5 наведені умовні позначення (схеми) логічних елементів, що реалізують логічне множення, логічне додавання і інверсію.

Рис 1.5.
Логічні елементи

Логічний елемент І (кон'юнктор) реалізує операцію логічного множення (рис. 1.5, а). Одиниця на виході цього елемента з'явиться тільки тоді, коли на всіх входах будуть одиниці.

Логічний елемент АБО (діз'юнктор) реалізує операцію логічного додавання (рис. 1.5, б). Якщо хоча б на одному вході буде одиниця, то на виході елемента також буде одиниця.

Логічний елемент НЕ (інвертор) реалізує операцію заперечення (рис. 1.5, в). Якщо на вході елемента О, то на виході 1 і навпаки.

Комп'ютерні пристрої, що виробляють операції над двійковими числами, і осередки, що зберігають дані, являють собою електронні схеми, що складаються з окремих логічних елементів. Більш детально ці питання будуть розкриті в курсі інформатики 10-11 класів.

приклад 3. Проаналізуємо електронну схему, т. Е. З'ясуємо, який сигнал повинен бути на виході при кожному можливому наборі сигналів на входах.

Рішення. Всі можливі комбінації сигналів на входах А до В внесемо в таблицю істинності. Простежимо перетворення кожної пари сигналів при проходженні їх через логічні елементи і запишемо отриманий результат в таблицю. Заповнена таблиця істинності повністю описує розглянуту електронну схему.

Таблицю істинності можна побудувати і за логічного виразу, відповідного електронній схемі. Останній логічний елемент в даній схемі - кон'юнктор. У нього надходять сигнали від входу Л і від інвертора. У свою чергу, в інвертор надходить сигнал від входу В. Таким чином,

Скласти повніше уявлення про логічних елементах і електронних схемах вам допоможе робота з тренажером «Логіка» (http: // kpolyakov. Narod. Ru / prog / logic. Htm).

Найголовніше

Висловлення - це пропозиція на будь-якій мові, зміст якого можна однозначно визначити як істинне або помилкове.

Основні логічні операції, певні над висловлюваннями: інверсія, кон'юнкція, диз'юнкція.

Таблиці істинності для основних логічних операцій:

При обчисленні логічних виразів спочатку виконуються дії в дужках. Пріоритет виконання логічних операцій: