COMPSCI 1JC3 Lecture Notes - Lecture 4: Proof Calculus, Boolean Expression, Propositional Calculus
11 Jun 2018
School
Department
Course
Professor
4 Logic
- What is logic?
o The study if the principles underling sound reasoning
o Underlying mathematical reasoning
o Branch of mathematics underlying computing
o 1. Logic is a reasoning system with a language with a formal syntax and precise
semantics
o 2. Concepts of truth and logical consequences
o 3. A proof system for establishing statements that are true
- propositional logic
- Theoretical uses:
o To study computation, programming languages, software design
- Practical uses:
o To write precise documentation about software artifacts that can be stored and
manipulated
o To reason about software artifacts, to help with proof assistance
o To provide reasoning facilities in programming language
- Haskell; quantifier- free first- order logic
o Bool
▪ Either true or false
▪ A Boolean expression is also called a formula
▪ Ex true && false
▪ Ex predicate 1==2
o Boolean functions
▪ Is a function of a type of the following form: Bool-> Bool-> Bool
▪ There are three Boolean functions
• Negation: not
• Conjunction: &&
• Disjunction or (||)
▪ All Boolean functions are constructed using:
• Not and and
• Not and or
• Nand (opposite of and, opposite of both being true)
• Nor (opposite of or, where or is at least one is true)
▪ There are 16 binary Boolean functions
o Predicates
▪ Function of the following form: t1-> …
o Conditional expressions
▪ An expression is an expression whose value depends on the value of the
Boolean expression
▪ If then else
▪ Conditional expressiuin allows code to be skipped
o Guarded function definitions
find more resources at oneclass.com
find more resources at oneclass.com
