Logic and Discrete Mathematics Exam Help - Revision history

Akerge: /* Proof techniques*/

2016-01-17T07:50:36Z

Proof techniques

← Older revision		Revision as of 10:50, 17 January 2016
Line 210:		Line 210:
	Please see yourself to the [http://logitext.mit.edu/tutorial interactive tutorial of the Sequent Calculus (LK)].		Please see yourself to the [http://logitext.mit.edu/tutorial interactive tutorial of the Sequent Calculus (LK)].

	== Proof techniques. Constructive and non-constructive proofs==		== Proof techniques ==

			A theorem is a statement that can be shown to be true. Theorem is true with a sequence of statements that form an argument, called a proof. To construct proofs, methods are needed to derive new statements from old ones. Rules of interference are the means used to draw conclusions from other assertions, tie together the steps of a proof.

			=== Constructive and non-constructive proofs===

	== Proofs by contraposition and contradiction==		== Proofs by contraposition and contradiction==

Akerge: /* Propositional calculus (PC) */

2016-01-16T19:55:46Z

Propositional calculus (PC)

← Older revision		Revision as of 22:55, 16 January 2016
Line 174:		Line 174:

	==Propositional calculus (PC)==		==Propositional calculus (PC)==

			Propositional Logic, or the Propositional Calculus, is a formal logic for reasoning about propositions, that is, atomic declarations that have truth values.

	=== Derivation in classical logic===		=== Derivation in classical logic===

			Classical propositional logic is a kind of propostional logic in which the only truth values are true and false and the four operators not, and, or, and if-then, are all truth functional. Therefore, by conversing the previous sentence we get, that propositional calculus uses more than four logical operators.

	==Semantics of predicate calculus==		==Semantics of predicate calculus==

Akerge: /* Logical equivalence */

2016-01-16T19:52:13Z

Logical equivalence

← Older revision		Revision as of 22:52, 16 January 2016
Line 29:		Line 29:
	! ''Equivalence'' !! ''Name''		! ''Equivalence'' !! ''Name''
	\|-		\|-
	\| p∧'''T'''≡p<br />p∨'''F'''≡p \|\| Identity laws		\| p ∧ '''T''' ≡ p<br />p ∨ '''F''' ≡ p \|\| Identity laws
	\|-		\|-
	\| p∨'''T'''≡'''T'''<br />p∧'''F'''≡'''F''' \|\| Domination laws		\| p ∨ '''T''' ≡ '''T'''<br /> p ∧ '''F''' ≡ '''F''' \|\| Domination laws
	\|-		\|-
	\| ~~p∨p≡p~~<br />p∧p≡p \|\| Idempotent laws		\| p ∨ p ≡ p <br />p∧p≡p \|\| Idempotent laws
	\|-		\|-
	\| ¬(¬p)≡p \|\| Double negation law		\| ¬(¬p) ≡ p \|\| Double negation law
	\|-		\|-
	\| ~~p∨q≡q∨p~~<br />p∧q≡q∧p \|\| Commutative laws		\| p ∨ q ≡ q ∨ p<br />p∧q≡q∧p \|\| Commutative laws
	\|-		\|-
	\| (~~p∨q~~)~~∨r≡p∨~~(~~q∨r~~)<br />(~~p∧q~~)~~∧r≡p∧~~(~~q∧r~~) \|\| Associative laws		\| (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)<br />(p ∧ q) ∧ r ≡ p ∧ (q ∧ r) \|\| Associative laws
	\|-		\|-
	\| p∨(~~q∧r~~)≡(~~p∨q~~)∧(~~p∨r~~)<br />p∧(~~q∨r~~)≡(~~p∧q~~)∨(~~p∧r~~) \|\| Distributive laws		\| p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)<br />p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) \|\| Distributive laws
	\|-		\|-
	\| ¬(~~p∧q~~)~~≡¬p∨¬q~~<br />¬(~~p∨q~~)~~≡¬p∧¬q~~ \|\| De Morgan's laws		\| ¬(p ∧ q) ≡ ¬p ∨ ¬q<br />¬(p ∨ q) ≡ ¬p ∧ ¬q \|\| De Morgan's laws
	\|-		\|-
	\| p∨(~~p∧q~~)≡p<br />p∧(~~p∨q~~)≡p \|\| Absorption laws		\| p ∨ (p ∧ q) ≡ p<br />p ∧ (p ∨ q) ≡ p \|\| Absorption laws
	\|-		\|-
	\| ~~p∨¬p≡~~'''T'''<br />~~p∧¬p≡~~'''F''' \|\| Negation laws		\| p ∨ ¬p ≡ '''T'''<br />p ∧ ¬p ≡ '''F''' \|\| Negation laws
	\|}		\|}

Akerge: /* Logical equivalences for quantifiers */

2016-01-16T19:39:32Z

Logical equivalences for quantifiers

← Older revision		Revision as of 22:39, 16 January 2016
Line 171:		Line 171:
	[https://goo.gl/olHWgn Example where ∀x.∃y.P(x,y) (¬≡) ∃y.∀x.P(x,y) ]		[https://goo.gl/olHWgn Example where ∀x.∃y.P(x,y) (¬≡) ∃y.∀x.P(x,y) ]

	[https://goo.gl/KXLDUR The meaning of the different possible quantifications involving two ~~varialbes~~.]		[https://goo.gl/KXLDUR The meaning of the different possible quantifications involving two variables.]

	==Propositional calculus (PC)==		==Propositional calculus (PC)==

Akerge: /* Conjunctive and Disjunctive Normal Form of propositional statements */

2016-01-16T19:36:25Z

Conjunctive and Disjunctive Normal Form of propositional statements

Aovtsinn: /* Validity and satisfiability of predicate statements */

2016-01-16T14:47:35Z

Validity and satisfiability of predicate statements

← Older revision		Revision as of 17:47, 16 January 2016
Line 180:		Line 180:

	=== Validity and satisfiability of predicate statements===		=== Validity and satisfiability of predicate statements===
			<u> Validity</u>

			An assertion in predicate calculus is logically valid (or simply valid) if it is true in every interpretation, that is if and only if it is true :

			- for all domains

			- for every propositional functions substituted for the predicates in the assertion

			Valid assertions in predicate logic play a role similar to tautologies in propositional logic.
			Example: <pre>∀x.(P(x)v¬P(x))</pre>
			<u>Satisfiability</u>

			An assertion in predicate calculus is satisfiable iff it is true:

			- for some domain

			- for some propositional functions that can be substituted for the predicates in the assertion

			Valid assertions in predicate logic play a role similar to tautologies in propositional logic.
			Example: [https://goo.gl/vgQ9EE link]

	== Sequent predicate calculus LK==		== Sequent predicate calculus LK==

Aovtsinn: /* Logical equivalences for quantifiers */

2016-01-16T14:41:41Z

Logical equivalences for quantifiers

← Older revision		Revision as of 17:41, 16 January 2016
Line 164:		Line 164:

	==Logical equivalences for quantifiers==		==Logical equivalences for quantifiers==
			Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions.
			We use the notation S ≡ T to indicate that two statements S and T involving predicates and quantifiers are logically equivalent.

			[https://goo.gl/ZLsWZe Examples]

			[https://goo.gl/olHWgn Example where ∀x.∃y.P(x,y) (¬≡) ∃y.∀x.P(x,y) ]

			[https://goo.gl/KXLDUR The meaning of the different possible quantifications involving two varialbes.]

	==Propositional calculus (PC)==		==Propositional calculus (PC)==

Aovtsinn: /* Predicates and quantifiers */

2016-01-16T14:35:48Z

Predicates and quantifiers

← Older revision		Revision as of 17:35, 16 January 2016
Line 134:		Line 134:

	==Predicates and quantifiers==		==Predicates and quantifiers==
			A predicate or propositional function is a description of the property (or properties) a variable or subject may have. A proposition may be created from a propositional function by either assigning a value to the variable or by quantification.
			Propositional logic cannot adequately express the meaning of all statements in mathematics and in natural language.
			<pre>
			Example:
			Having assumptions:
			• Every computer connected to the school network is functioning properly.
			• ELVIS is one of the computers connected to the school network.
			No rules of propositional logic allows us to conclude the truth of the statement
			ELVIS is functioning properly
			</pre>
			Extends propositional logic by
			• Individuals a, b, ... , ELVIS, ...

			• (Individual) variables x,y,...

			• Predicates(= propositional functions) P(x), Q(x), R(x,y), ...

			• Quantifiers ∀,∃

			A propositional function is a generalisation of proposition:
			• its argument stands for en element from its domain;

			• its value is True or False depending on the property of its argument(s).

	=== Bound and free variables===		=== Bound and free variables===

Aovtsinn: /* Bound and free variables */

2016-01-16T14:28:19Z

Bound and free variables

← Older revision		Revision as of 17:28, 16 January 2016
Line 136:		Line 136:

	=== Bound and free variables===		=== Bound and free variables===
			• The quantifiers are said to bind the variable x in the expressions ∀xP(x) and ∃xP(x). Variables in the scope of some quantifier are called bound variables. All other variables in the expression are called free variables.

			• A propositional function that does not contain any free variables is a proposition and has a truth value.

	==Logical equivalences for quantifiers==		==Logical equivalences for quantifiers==

Aovtsinn: /* Conjunctive and Disjunctive Normal Form of propositional statements */

2016-01-16T14:27:29Z

Conjunctive and Disjunctive Normal Form of propositional statements

← Older revision		Revision as of 17:27, 16 January 2016
Line 119:		Line 119:

	==Conjunctive and Disjunctive Normal Form of propositional statements==		==Conjunctive and Disjunctive Normal Form of propositional statements==
			A formula in conjunctive normal form (CNF) is a conjunction of clauses.
			<pre>Example of CNF: (p∨¬q∨r)∧(¬p∨¬r)∧q </pre>
			Similarly, one defines formulas in disjunctive normal form (DNF) by swapping the words
			’conjunction’ and ’disjunction’ in the definitions above.
			<pre>Example of DNF: (¬p∧q∧r)∨(¬q∧¬r)∨(p∧r) </pre>
			<u>Transformation into CNF :</u>
			Every propositional formula can be converted into an equivalent formula that is in CNF.
			<pre>Example: Transform the following formula into CNF: ¬(p → q) ∨ (r → p)
			1) Express implication by disjunction and negation: ¬(¬p∨q) ∨ (¬r ∨ p)
			2) Push implication by disjunction and negation: (¬¬p∧¬q) ∨ (¬r ∨ p); (p∧¬q) ∨ (¬r ∨ p)
			3) Convert to CNF by associative and distributive laws: (p∨¬r ∨ p)∧(¬q¬r ∨ p)
			4) Optionally simplify by commutative and idempotent laws: (p∨¬r)∧(¬q(p∨¬r)
			and by commutative and absorption laws: p∨¬r</pre>

	==Predicates and quantifiers==		==Predicates and quantifiers==

← Older revision		Revision as of 22:36, 16 January 2016
Line 120:		Line 120:
	==Conjunctive and Disjunctive Normal Form of propositional statements==		==Conjunctive and Disjunctive Normal Form of propositional statements==
	A formula in conjunctive normal form (CNF) is a conjunction of clauses.		A formula in conjunctive normal form (CNF) is a conjunction of clauses.
	<pre>Example of CNF: (~~p∨¬q∨r~~)∧(~~¬p∨¬r~~)∧q </pre>		<pre>Example of CNF: (p ∨ ¬q ∨ r) ∧ (¬p ∨ ¬r) ∧ q </pre>
	Similarly, one defines formulas in disjunctive normal form (DNF) by swapping the words		Similarly, one defines formulas in disjunctive normal form (DNF) by swapping the words
	’conjunction’ and ’disjunction’ in the definitions above.		’conjunction’ and ’disjunction’ in the definitions above.
	<pre>Example of DNF: (~~¬p∧q∧r~~)∨(~~¬q∧¬r~~)∨(~~p∧r~~) </pre>		<pre>Example of DNF: (¬p ∧ q ∧ r) ∨ (¬q ∧ ¬r) ∨ (p ∧ r) </pre>
	<u>Transformation into CNF :</u>		<u>Transformation into CNF :</u>
	Every propositional formula can be converted into an equivalent formula that is in CNF.		Every propositional formula can be converted into an equivalent formula that is in CNF.
	<pre>Example: Transform the following formula into CNF: ¬(p → q) ∨ (r → p)		<pre>Example: Transform the following formula into CNF: ¬(p → q) ∨ (r → p)
	1) Express implication by disjunction and negation: ¬(~~¬p∨q~~) ∨ (¬r ∨ p)		1) Express implication by disjunction and negation: ¬(¬p ∨ q) ∨ (¬r ∨ p)
	2) Push implication by disjunction and negation: (~~¬¬p∧¬q~~) ∨ (¬r ∨ p); (~~p∧¬q~~) ∨ (¬r ∨ p)		2) Push implication by disjunction and negation: (¬¬p ∧ ¬q) ∨ (¬r ∨ p); (p ∧ ¬q) ∨ (¬r ∨ p)
	3) Convert to CNF by associative and distributive laws: (~~p∨¬r~~ ∨ p)∧(~~¬q¬r~~ ∨ p)		3) Convert to CNF by associative and distributive laws: (p ∨ ¬r ∨ p) ∧ (¬q ¬r ∨ p)
	4) Optionally simplify by commutative and idempotent laws: (~~p∨¬r~~)∧(¬q(~~p∨¬r~~)		4) Optionally simplify by commutative and idempotent laws: (p ∨ ¬r) ∧ (¬q (p ∨ ¬r)
	and by commutative and absorption laws: ~~p∨¬r~~</pre>		and by commutative and absorption laws: p ∨ ¬r</pre>

	==Predicates and quantifiers==		==Predicates and quantifiers==