well formed formula DMS by Komal rokade.pptx

Discrete Mathematics structure

1. Well-Formed Formula(WFF) BY Ms. Komal V Rokade .

2. Well-Formed Formula(WFF) Well-Formed Formula(WFF)  is an expression consisting of variables( capitalletters ),parentheses, and connective symbols. An expression is basically a combination of operands & operators and here operands and operators are the connective symbols.

3. Below are the possible Connective Symbols: ¬ (Negation) ∧ (Conjunction) ∨ (Disjunction) ⇒ (Rightwards Arrow) ⇔ (Left-Right Arrow)

4. Statement Formulas 1.  Statements that do not contain any connectives are called  Atomic  or  Simple  statements and these statements in themselves are  WFFs .  For example, P, Q, R, etc. 2.  Statements that contain one or more primary statements are called  Molecular  or  Composite  statements.  For example, 

5. 3. If P and Q are two simple statements, then some of the Composite statements which follow WFF standards can be formed are: ->    ¬P  ->    ¬Q  ->    (P ∨ Q)  ->    (P ∧ Q) ->    (¬P ∨ Q)  ->    ((P ∨ Q) ∧ Q) ->    (P ⇒ Q) ->    (P ⇔ Q) ->    ¬(P ∨ Q) ->    ¬(¬P ∨ ¬Q)

6. Rules of the Well-Formed Formulas 1 .A Statement variable standing alone is a  Well-Formed Formula(WFF) .  For example – Statements like P, ∼P, Q, ∼Q are themselves Well Formed Formulas. 2. If ‘P’ is a WFF then ∼P is a formula as well. 3. If P & Q are WFFs, then (P∨Q), (P∧Q), (P⇒Q), (P⇔Q), etc. are also WFFs.

7. Example Of Well Formed Formulas:

8. Examples which may seem like a WFF but they are not WFF (P) , ‘P’ itself alone is considered as a WFF by Rule 1 but placing that inside parenthesis is not considered as a WFF by any rule. ¬P ∧ Q , this can be either (¬P∧Q) or ¬(P∧Q) so we have ambiguity in this statement and hence it will not be considered as a WFF. Parentheses are mandatory to be included in Composite Statements.

9. ((P ⇒ Q)) , We can say (P⇒Q) is a WFF and let (P⇒Q) = A, now considering the outer parentheses, we will be left with (A), which is not a valid WFF. Parentheses play a really important role in these types of questions. (P ⇒⇒ Q) , connective symbol right after a connective symbol is not considered to be valid for a WFF. ((P ∧ Q) ∧)Q) , conjunction operator after (P∧Q) is not valid.

10. ((P ∧ Q) ∧ PQ) , invalid placement of variables(PQ). (P ∨ Q) ⇒ (∧ Q) , with the Conjunction component, only one variable ‘Q’ is present. In order to form an operation inside a parentheses minimum of 2 variables are required.