Hire Experts For Answers

Order Now#### Related Study Services

- Homework Answers
- Coursework writing help
- Term paper writing help
- Writing Help
- Paper Writing Help
- Research paper help
- Thesis Help
- Dissertation Help
- Case study writing service
- Capstone Project Writing Help
- Lab report Writing
- Take my online class
- Take my online exam
- Do my test for me
- Do my homework
- Do my math homework
- Online Assignment Help
- Do my assignment
- Essay Writing Help
- Write my college essay
- Write my essay for me

DESCRIPTION

Posted

Modified

Viewed
15

INTRODUCTION TO COMPUTATION THEORY AND LOGIC exam needs to be taken, online exam between the hours of 1400 and 1700, previous year exam example provided

Attachments

Show all work.
Question 1.
1a (8 marks).
Construct a CNF (not DNF) with the following truth-table.
X Y Z
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
X Y Z
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
1b (12 marks).
Construct a resolution proof that the following CNF is inconsistent
UWX, UW X , U WX , U W X, UY, U Y , V WY, V WY ,
V W Y, V W Y , V X, V X
Question 2
Consider a first order theoryK which has a multiplication operator ×, usually omitted so xy
means x× y, and has various proper axioms to ensure an equality theory (with = representing
equality). It also has an axiom (associativity)
∀x1∀x2∀x3(x1(x2x3)) = ((x1x2)x3)
Let A′, A,B′, B be the formulae below
A′(x1) : ∀x2(x1x2 = x2), A(x1) : ∃x1A
′(x1), B
′(x1) : ∀x2(x2x1 = x2), B(x1) : ∃x1B
′(x1)
and let K+A, K+A+B be the theories formed by adding A (respectively A,B) as an axiom
(axioms).
2a (8 marks). Show that the interpretation I with domain {a, b}, =I the identity relation on
{a, b}, and
×I a b
a a b
b a b
is a model of K + A. (Show this informally without bringing in the idea of ‘snapshots.’)
2b (4 marks). Determine whether or not it is a model of K + A+ B.
2c (8 marks). Give a careful proof within K as a first-order theory (with equality: you may
use equality reasoning informally) that
A′(x1) ∧ A
′(x3) ∧ B
′(x4) =⇒ x1 = x3.
(Hint: the proof should be guided by the fact that x1x4 = x1 = x4.)
Question 3.
3a (6 marks). Prove that, in any first-order theory K, under a certain condition
A(t) =⇒ ∃xiA(xi)
is a theorem, stating the required condition.
3b (4 marks). Give an example showing that (3a) is not true (in every interpretation) if that
condition is not met.
3c (5 marks). (Note: a countable set D is one which can be listed as a countable sequence
d1, d2, . . ., so for every nonempty subset X of D there is a smallest i such that di ∈ X.)
Suppose that K is a first-order theory, P (x1, x2) an atomic formula, and M is a model of
K, with countable domain D, such that
M |= ∃x2P (x1, x2)
Show that for every a ∈ D there exists a b ∈ D such that
PM(a, b)
is true.
3d (5 marks) (Continuing 3c).
Show that one can define a function F : D → D such that for every a ∈ D,
M |= P (a, F (a)).
(F can be used, for example, in connection with Skolem functions.)
Question 4
Referring to the proof in the notes that it is consistent to assume that infinite integers exist,
the idea was to extend PA with a new constant symbol a plus infinitely many formulae which
together imply that a is infinite.
4a (6 marks) Construct an interpretation of this extension, with domain N∪{∞}, extending
the definitions of s(),+,×, so that every axiom of PA except possibly Axiom 4 (induction), is
true in this interpretation. Also, you may ignore the equality axioms.
4a (14 marks) Show that the 7 axioms mentioned in (4a) are true in the interpretation. You
may skip the induction axiom.

Explanations and Answers
0

No answers posted

### Post your Answer - free or at a fee

**NB: **Post a homework question for free and get answers - free or paid homework help.

Get answers to: Need An Online Exam Taken Between The Hours Of 1400 And 1700 May 5Th. or similar questions only at Tutlance.

Related Questions

- Apply The Ica Method To The Fetal Ecg Data In
- Enterprise Computing - Creating Network For A Mid Size Company
- C++ Assignement That Allow To Found The Best Route Between Nodes
- Networking For A Call Center Project
- Data Structures Java Eclipse/++
- Mips And Vhdl Homework + Microarchitecture
- Mips And Vhdl Homework + Microarchitecture
- Mips And Vhdl Homework + Microarchitecture
- Ap Create Task Comp Sci Principles
- Java Programing Assessment Due On 29
- Scala Asignment Using Intellij
- Java Project That Calculates The Final Grades Of Students And And Making A Gui For Those Calculations.
- What Are The Three Parts Of A System Vision Document?
- Assembly Language (Arm Ual) In Visual Emulator App (Very Short, 10 Line Code)
- State Based / Case Based Testing & Using Selenium For Web Application Testing
- Java Programing Assessment Due On 29
- Simulating A Mail Delivery System - Java Programming Assignment
- Software Quality Assurance And Testing
- Bookstore Javafx Project (With Mysql)
- Dvwa Configuration, Mysql Injection And Command Injection
- Cybersecurity - Ipsec Vpn Setup
- Cybersecurity Firewall Lab Report
- Creating A Cluster Analysis For Dataset In R
- Assignment Mips Assembly Language Coding
- Buy Or Build A Computer For My Cpt 209 Class
- Create Performence Task Project
- Mips Assembly Language And Computer Architecture
- I Need Help With My Computer Assignment .
- Vhdl Lab Assignment Using Quartus 2
- Python Coding Assignment For Class
- Massive Mimo Detection Algorithms Simulated On Matlab With Different Parameters
- Penetration Test Report Prepared For Hotel Dorsey
- A C++ Assignment That Uses Structs, Const, .H, And .Cpp Files All In One.
- M-Tree Data Loading And Modelling Have To Be Done Step By Step Because Professor Need To Valid Each Step
- Create A Python Program That Will Perform The Following Tasks. In Addition Summarize The Approach Taken, Show All Work.
- Cs-330 Comp Graphic And Visualization
- Google's Tenser Processing Unit And Acceleration Of Deep Neutral Networks
- Ml- Machine Learning: Regression Model Or Classification To Be Developed With Jupyter
- Build Simple Model Of Diffusion-Limited Growth Due To Matsuura [Mat00], Further Explored By Tronnolone Et Al. [Tts+18].
- Richardson School District Network Design Project - Logical Topology Assignment Help
- Implementing A Client Server Chat Room Using Tcp That Handles Messaging And Transferring Files Between Multiple Clients
- Polling Data Data Structures Lab With Priority Queues And Heaps
- System Integration And Architecture 1
- Arithmetic Expression Parse Tree Implementation
- Binary Search Tree Assignment
- Assembly Language (Arm) Using Visual Emulator
- Need Someone To Do My Haskell Programming Assessment
- Machine Language Course. This Assignment Focuses On Assembly Language(Armv8), Datapath And Control Diagram Of Processor.
- Polling Data Data Structures Lab With Priority Queues And Heaps
- Polling Data Data Structures Lab With Priority Queues And Heaps