# What is a First-Order Logic? - University of Pittsburgh

CS1502 Formal Methods in Computer Science Lecture Notes 16 Review for Exam2 continued Theory of Computation Introduction 10.25 Is the following a logical truth? ~exist z Small(z) exist z ~Small(z) 1. Every cube is to the left of every tet.

2. Every small cube is in back of a large cube. 3. Some cube is in front of every tet. 4. A large cube is in front of a small cube. 11.16 11.16 5. Nothing is larger than everything which is 6. Every cube in front of every tet is large.

7. Everything to the right of a large cube is small. 8. Nothing in back of a cube and in front of a cube is large. 11.16 9. Anything with nothing in back of it is a cube. 10. Every dodec is smaller than some tet. 11.20 1. Nothing to the left of a is larger than everything to the left of b

3. The same things are left of a as are left of b. 11.20 7. Only dodecs are larger than everything else. Answer in solution: Is this correct? Hmm. Necessary S is always true

Possible Satisfiable S could be true Equivalence Consequence S and S always have the same truth values Whenever P1

Pn are true, Q is also true Tautological Translate sentences into propositional logic using TFF algorithm S is a tautology S is Tautologically possible

S and S are Tautologically equivalent Q is a tautological consequence of P1Pn First Order (FO) Replace predicates with nonsense names S is an FO validity

S is FO possible (FO satisfiable) S and S are FO equivalent Q is a FO consequence of P1Pn Logical

S is logically necessary (a logical truth) (logically valid) S is logically possible (satisfiable) S and S are logically equivalent

Q is a logical consequence of P1Pn Theory of Computation Sipser text covers automata, computability, and complexity CS1502: automata (chapter 1) CS1511 uses the same text Theory of Computation What are the fundamental capabilities and limitations of computers?

Complexity Theory Classes of problem difficulty (sorting < sched) The **problems**, not the code If can show a problem is in a certain class: easy keep working on an efficient solution! hard give up, you wont find a fast solution Perhaps modify the problem into an easier one; maybe solving that is good enough for whats needed Cryptography want problem so decoding is intractable

Still important/answered questions. As new models of computation arise: what is tractable/intractable? Computability Theory Which problems can be solved on a computer? Turing Machine: Abstract away from particular hardware, OS, PL, algorithm Can compute anything that is a Turing machine Automata Theory

Begins with the question, what is a computer? Real computers are too complex and messy to model. So, we define computational models (idealized computer) Finite Automata; Finite-State Machines Simplest machines Cannot compute everything, but operations are cheap and efficient. So, use them if you can!

Used in text processing, compilers, hardware design, etc. Composed of states and transitions between states

## Recently Viewed Presentations

• گروه آموزشی تربیت بدنی و علوم ورزشی دانشکده علوم تربیتی و روانشناسی 2012/12/26
• Fry Elementary School 1st Grade-Q1 an big be blue Be happy. I ate an apple. ... Times New Roman Comic Sans MS Tempus Sans ITC Default Design PowerPoint Presentation PowerPoint Presentation PowerPoint Presentation PowerPoint Presentation PowerPoint Presentation PowerPoint Presentation PowerPoint...
• Pork Terminology & Breeds M. Marler Fall 2011 Swine Terminology Boar-Mature male pig Sow-Mature female pig Barrow-Castrated male pig Gilt-Young, immature female pig Farrowing-The act of giving birth in swine Swine Terminology Boar-Mature male pig Sow-Mature female pig Barrow-Castrated male...
• * * Continuons par la demande exprimée par le département de la conservation restauration du musée : les soutenir dans leur démarche afin d'imposer certains principes dans un projet déjà en en phase finale de conception avec les options suivantes...
• asset replacement with different technology or modified functionality e.g. reduced capacity and supported by non-network options. asset replacement using similar technology/functionality: partial replacement; brownfield, or greenfield. Combined options, implemented together or staged for option value and reduced service cost. Tuesday,...
• Earth Science draws from all other areas of science such as physics, chemistry, biology, astronomy, meteorology, etc. 3. Earth Science requires a consideration of vast amounts of time with sequencing of events (chronology) and ages. ... Earth Systems 3209/ Earth...
• Avoid the room being too busy, keep toys in containers, avoid busy rugs, and too bright of colors.-snack. Make sure the child is not taking a nap or too long of a nap that interferes with night time sleep. Does...
• If you guess it, you will be definitely right: it is a presentation about presentations. I shall not emphasize about the outmost importance of making presentations as a scientist or the role of presentations in the industrial and business worlds....