Difference between revisions of "Logic and Computation"
From Wiki Notes @ WuJiewen.com, by Jiewen Wu
| Line 20: | Line 20: | ||
* unless: it is usually disjunction \/, e.g., I die unless I breathe. It means in order to guarantee that "I die", I must not breathe. Hence, it is: "die \/ breathe", which is logically equivalent to "~breathe => die". | * unless: it is usually disjunction \/, e.g., I die unless I breathe. It means in order to guarantee that "I die", I must not breathe. Hence, it is: "die \/ breathe", which is logically equivalent to "~breathe => die". | ||
| − | * implications: it is debatable whether implications like p=>q correspond to "if p then q", as it is better known as an variant to "~p \/ q". | + | * implications: it is debatable whether implications like p=>q correspond to "if p then q", as it is better known as an variant to "~p \/ q". Let's take it as "if p then q", or "p only q", or "q when p", or more precisely, p is sufficient for q while q is necessary for p. '''Note that "q if p" (if p then q) is "p=>q", and "p only if q" is "p=>q".''' |
==References== | ==References== | ||
[[Category:Logic and Reasoning]] | [[Category:Logic and Reasoning]] | ||
Revision as of 10:57, 4 August 2009
Introduction
This page is to setup to summarize fundamentals of common logics.
Every logic consists of its syntax, semantic and proof theories.
Boolean Logic
It is also known as propositional logic, where a countably infinite alphabet of boolean variables can take two values either true or false.
Syntax
- Constants: true and false;
- Propositional letters;
- Connectives;
- Brackets.
A well-formed formula (wff) is defined inductively as follows:
- prime propositions including proposition letters, constants;
- any compound propositions for formulas p and q: ~p, p/\q, p\/q, p=>q, p<=>q.
Normally we assume the precedence of operators as brackets, ~, /\, \/, =>, <=>. The right associativity is assumed too, e.g., p=>(q=>r).
Formalization
Natural language is ambiguous, and it remains to discuss how to formalize our language into logic formulas. We simply look at some of the examples. Note that sometimes we are unable to rigorously capture the meaning in natural languages.
- unless: it is usually disjunction \/, e.g., I die unless I breathe. It means in order to guarantee that "I die", I must not breathe. Hence, it is: "die \/ breathe", which is logically equivalent to "~breathe => die".
- implications: it is debatable whether implications like p=>q correspond to "if p then q", as it is better known as an variant to "~p \/ q". Let's take it as "if p then q", or "p only q", or "q when p", or more precisely, p is sufficient for q while q is necessary for p. Note that "q if p" (if p then q) is "p=>q", and "p only if q" is "p=>q".
