 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Задания к семестровой работе
|
|
Вариант №1
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Исчисление – это (а) содержательная; (б) формальная теория.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на последнем символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | |||
| –– | q 01 C | |||
| q 21 L | q 11 C | |||
Вариант №2
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Алфавит любой логической теории включает: (а) логические символы; (б) специальные символы; (в) нелогические символы; (г) технические символы.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на первом символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | |||
| –– | q 01 C | |||
| q 21 R | q 11 C | |||
Вариант №3
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
К логическим символам относятся: (а) пропозициональные буквы; (б) кванторы; (в) предикатные буквы; (г) пропозициональные связки.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на последнем символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | |
| q 01 C | |
| q 11 L |
Вариант №4
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
В состав нелогических символов языка исчисления предикатов входят: (а) кванторы; (б) пропозициональные переменные; (в) функциональные символы; (г) предметные переменные.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на первом символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | |
| q 01 C | |
| q 11 R |
Вариант №5
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
В состав логических символов языка исчисления высказываний входят: (а) кванторы; (б) пропозициональные связки; (в) пропозициональные переменные.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на последнем символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | |||
| –– | q 00 C | |||
| q 20 L | q 11 C | |||
Вариант №6
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
В состав любой содержательной логической теории обязательно входят: (а) алфавит; (б) множество правильно построенных выражений; (в) аксиомы.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на последнем символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | |||
| –– | q 01 C | |||
| q 20 L | q 11 C | |||
Вариант №7
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Обязательными символами алфавита любой теории 1-го порядка являются: (а) функциональные буквы; (б) предикатные буквы; (в) предметные константы.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на первом символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | |||
| –– | q 00 C | |||
| q 20 R | q 11 C | |||
Вариант №8
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
В множество правильно построенных выражений языка исчисления высказываний входят: (а) термы; (б) формулы; (в) всевозможные последовательности символов языка.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на первом символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | |||
| –– | q 01 C | |||
| q 20 R | q 11 C | |||
Вариант №9
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
В состав формулы исчисления предикатов могут входить: (а) термы; (б) пропозициональные переменные; (в) предикаты; (г) кванторы.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на последнем символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | |
| q 00 C | |
| q 10 L |
Вариант №10
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
В состав терма могут входить: (а) функциональные буквы; (б) предметные константы; (в) пропозициональные переменные; (г) логические связки.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на последнем символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | |
| q 01 C | |
| q 10 L |
Вариант №11
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Исчисление высказываний является: (а) разрешимой теорией; (б) неразрешимой теорией.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на первом символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | |
| q 00 C | |
| q 10 R |
Вариант №12
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Исчисление предикатов является: (а) разрешимой теорией; (б) неразрешимой теорией.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на первом символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | |
| q 01 C | |
| q 10 R |
Вариант №13
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Формула исчисления высказываний называется выполнимой, если она принимает значение «истина» (а) на любых наборах значений входящих в неё пропозициональных переменных; (б) хотя бы на одном наборе значений входящих в неё пропозициональных переменных.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается перед первым символом слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | q 3 | ||
| q 20 R | q 30 L | q 00 C | ||
| –– | q 21 R | q 30 L |
Вариант №14
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Формула исчисления высказываний называется опровержимой, если она принимает значение «ложь» (а) на любых наборах значений входящих в неё пропозициональных переменных; (б) хотя бы на одном наборе значений входящих в неё пропозициональных переменных.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается перед первым символом слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | q 3 | ||
| q 20 R | q 30 L | q 01 C | ||
| –– | q 21 R | q 30 L |
Вариант №15
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Пусть А и В – формулы. Утверждение «В логически следует из А» справедливо, если (а) А истина и В истина; (б) А истина, а В ложна; (в) А ложна, а В истина.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается за последним символом слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | q 3 | ||
| q 20 L | q 30 R | q 00 C | ||
| –– | q 21 L | q 30 R |
Вариант №16
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Пусть А и В – формулы, несовместимые по истинности, но совместимые по ложности. Тогда А и В находятся в отношении (а) противоречия; (б) противоположности; (в) подпротивоположности.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается за последним символом слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | q 3 | ||
| q 20 L | q 30 R | q 01 C | ||
| –– | q 21 L | q 30 R |
Вариант №17
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Секвенция вида «А 1, А 2, …, Аn |‑ B» означает, что (а) В – теорема; (б) А 1, А 2, …, Аn выводимо из В; (в) из А 1, А 2, …, Аn следует В; (в) В выводимо из А 1, А 2, …, Аn.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается перед первым символом слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | q 3 | ||
| q 20 R | q 31 L | q 00 C | ||
| –– | q 21 R | q 31 L |
Вариант №18
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Теорема – это (а) формализация понятия «логического следования»; (б) формализация понятия «логического закона»; (в) последняя формула в доказательстве; (г) последняя формула в любом выводе.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается за последним символом слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | q 3 | ||
| q 20 L | q 31 R | q 00 C | ||
| –– | q 21 L | q 31 R |
Вариант №19
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Метод Вонга основан на следующей выводимой секвенции: (а) А, В |‑ A; (б) A Ú B, C ÚØ B |‑ A Ú C; (в) A, A É B |‑ B.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается перед первым символом слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | q 3 | q 4 | |
| q 20 R | q 00 L | q 40 L | q 40 L | |
| –– | q 31 R | q 30 R | q 01 L |
Вариант №20
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Формула исчисления предикатов называется замкнутой, если ни одна предметная переменная в ней не является (а) связанной; (б) свободной.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на первом символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | q 3 | q 4 | |
| –– | q 01 L | q 40 L | q 40 L | |
| q 20 R | q 31 R | q 30 R | q 01 L |
Вариант №21
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Терм называется замкнутым, если он не содержит в своем составе (а) предметных констант; (б) предметных переменных.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается за последним символом слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | q 3 | q 4 | |
| q 20 L | q 00 R | q 40 R | q 40 R | |
| –– | q 31 L | q 30 L | q 01 R |
Вариант №22
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
К простейшим функциям в теории алгоритмов относятся: (а) константа; (б) нуль-функция; (в) любая рекурсивная функция; (г) проектирующая функция.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на последнем символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | q 3 | q 4 | |
| –– | q 01 R | q 40 R | q 40 R | |
| q 20 L | q 31 L | q 30 L | q 01 R |
Вариант №23
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
В тезисе Чёрча утверждается, что всякая эффективно вычислимая функция является (а) простейшей; (б) примитивно-рекурсивной; (в) частично-рекурсивной.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
4. Задана формула исчисления предикатов и множество М ={ a, b }. Привести формулу к предваренной нормальной форме. Определить, является ли формула на множестве М (а) выполнимой; (б) опровержимой; (в) истинной; (г) невыполнимой? Вычислить значение истинности формулы на множестве М со следующей интерпретацией предикатов: P (a)=«и», P (b)=«л», R (a)=«л», R (b)=«и», Q (a, a)=«и», Q (a, b)=«л», Q (b, a)=«л», Q (b, b)=«л».
5. Доказать или опровергнуть выводимость секвенции в исчислении предикатов методом: (а) аналитических таблиц; (б) резолюции (построив сначала предваренную нормальную форму и универсальное замыкание для каждой посылки и отрицания заключения).
6. Задана программа машины Тьюринга (q 1– начальное состояние, q 0– заключительное состояние управляющего устройства). Определить, какие действия выполняет эта машина с произвольным (в том числе и пустым) словом в алфавите A ={1}, если в начальной конфигурации головка устанавливается на первом символе слова. Записать последовательность конфигураций машины для слова Р =111.
| q 1 | q 2 | |||
| q 01 C | q 00 C | |||
| q 20 R | q 11 C | |||
Вариант №24
1. Вычеркните все лишнее. Сформулируйте и запишите полное определение выделенного понятия.
Математическими моделями понятия «алгоритм» являются: (а) таблицы истинности; (б) частично-рекурсивные функции; (в) алгорифмы Маркова; (г) аналитические таблицы; (д) машины Тьюринга.
2. Определить, являются ли формулы совместимыми по истинности, по ложности и следуют ли они одна из другой.
; 
3. Доказать или опровергнуть выводимость секвенции в исчислении высказываний методом: (а) натурального ИС; (б) Вонга; (в) резолюции.
Дата публикования: 2015-03-26; Прочитано: 1015 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
