exam in discrete math

A1Homework_01

FrmlMeth.SoftwareEXLSGroupCASpringSemester2018CO-4262018-740AM1.zip

Home >Mathematics homework help >Calculus homework help >exam in discrete math

Weeks 6 and 7 Overview.htm

Overview Week Five

Week Five: Sep 11- Sep 17

Introduction

This unit will teach how to use propositional calculus to simplify statements of requirements.

Learning Objectives: Related course level objectives: 2 and 3

After completing the tasks of Module 5:

The student will be able to use the Rules of Inference to simplify propositional expressions.
The student will be able to use propositional calculus to construct proofs to show whether or not a conclusion follows from a set of premises.

Tasks: To achieve the learning objectives of this module, you must do the following:

Print this page, and check off items as you complete them.
Read sections 3.4 in Ince.
Read the notes on Propositional calculus.
Do the homework assignment on sections 3.4 Part 1.
Participate and lead (start threads and reply to threads) the discussion on Requirements and Propositional Calculus-Section 3.4 in the Content Forum of the Discussion Tool.
Take the Quiz 1 via the Quizzes tool.
Do the homework assignment on sections 3.4 Part 2.

USING RULES OF INFERENCE.doc

USING RULES OF INFERENCE

Rules of inference are used to simplify expressions either to:

· TRUE – in which case a tautology has been found;

· FALSE – in which case a contradiction has emerged.

They are also used to support the reasoning process during requirements analysis.

Proofs consist of lines of TRUE propositions either assumed true and labeled symbolically or derived to be TRUE by means of applying rules of inference to earlier TRUE propositions and identifying this information in the form: [TRUE proposition, rules of inference used].

System specifications and statements of requirements contain a large number of fragments where simplification can make the meaning of natural language statements clearer.

Another way that the transformation from natural language into propositional calculus aids the analyst is with reasoning.

· Reasoning involves identifying a set of premises and a conclusion and then showing that the conclusion logically follows from the premises.

· By examining premises and attempting to deduce conclusions, the analysts are able to check the completeness of a specification and discover inconsistencies.

The relationship between premises and a conclusion is written in the form:

P1,P2,P3,…Pn |- C

Which states that the conclusion C logically follows from the premises P1,P2,P3,…Pn

There are two methods for demonstrating that a conclusion follows from the premises.

1. Transform the premises and conclusions into a propositional form and simplify by means of the laws of inference.

P1,P2,P3,…Pn |- C

Can be rewritten as:

P1 ^ P2 ^P3 ^…^Pn => C

(^ replaces the comma; => replaces the |-)

If we can show that P1 ^ P2 ^P3 ^…^ Pn => C is always TRUE (a tautology), then C is TRUE.

NOTE: Typically, the premises alone are not enough to validate the derivation. Propositional expressions from the system specification (S1,S2,…Sm) will also be required. Then it will be necessary to show:

P1 ^ P2 ^P3 ^…^Pn ^ S1^S2^…^Sm => C

Truth Table for 3.4.doc

¬ ValveOpened	startup	monitoring	¬ ValveOpened V startup V monitoring
TRUE	TRUE	TRUE	TRUE
TRUE	TRUE	FALSE	TRUE
TRUE	FALSE	TRUE	TRUE
TRUE	FALSE	FALSE	TRUE
FALSE	TRUE	TRUE	TRUE
FALSE	TRUE	FALSE	TRUE
FALSE	FALSE	TRUE	TRUE
FALSE	FALSE	FALSE	FALSE

Where is ¬ ValveOpened V startup V monitoring TRUE?

(All rows but the last one)

For what values of the variables is :

(2) ValveOpened Λ ¬ startup Λ ¬ monitoring

TRUE?

ValveOpened is true in the YELLOW rows.

¬ startup is true in the PINK rows

¬ monitoring is true in the TURQUOISE rows

So what values of the variables are both (1) and (2) TRUE? No place. Hence the contradiction.

ProofTemplate.doc

PR	Reference	Rule
1	PR
2	1
3	2
4	3
5	4
6	5
7	6
8	7

RULES+OF+INFERENCE.docx

RULES OF INFERENCE

= or1 = or2 =or3

= or4 or5

=and1 =and2 =and3

=and4 =and5

=comm =comm =comm

=rassoc =lassoc

=dist =dist

=DeM =DeM

=neg =exmid =contr

=impl implies impliesnot

=equal

e =exor

equiv

ØØ

true

false

p1,

p2,

p1)

(p2

p2)

(p1

true

p2,

p2)

(

true

false

p2)

(

p3)

(

p2)

(p1

true

p3)

(

p2)

(p1

p3)

(

p3)

(

p3)

(p1

p2)

(p1

false

p3)

(p1

p2)

(p1

p2)

(

p2)

(

PROPOSITIONAL_CALCULUS_Section_3.4-2014.docx

PROPOSITIONAL CALCULUS

EXAMPLE – Section 3.4

EX: Translate the following into propositional calculus:

If the inlet valve is open, then the system is switched to OPEN and the outlet valve is closed if the monitoring system is functioning.

Is the answer:

InValveOpen => (MonSysFunctioning => open Λ OutletClosed)

OR is it the following?

InValveOpen => (open Λ (MonSysFunctioning => OutletClosed)

Which is correct? Translating ambiguous requirements into something precise forces the analyst to ask the customer questions about the meaning. Very close attention to the textual requirements is necessary when constructing a formal system specification.

To help us with this precision and to allow us to simplify propositions and to check whether specific properties of a system specification hold, a number of rules of inference are required. The Rules of Inference are defined in another document (named: Rules of Inference), but to help you understand that document, see the following.

a>b,b>c trans >

a>c

The above is one of the Rules. It is read as:

“IF a>b AND b>c THEN a>c” which is the transitive property of >. Note, the => operator is implication, and it defines the relationship between the numerator and the denominator in the Rules of Inference.

In the inference rules, p1, p2, and p3 represent propositional expressions. We primarily use the rules of inference to simplify expressions to true, which means we found a tautology, or to false, which means we found a contradiction.

We will use a proof layout to simplify these propositional expressions using the rules of inference. We start from a given statement we assume to be true (the premise), and applying only rules of inference or other true propositions, we simplify the expression. Note we specify what proposition we derived from and what rule was used on the right hand side of the proof.

A simple example:

Given: (open V closed) Λ open

We want to simplify the expression to either True or False.

Solution:

[pr] (open V closed) Λ open

[1] open Λ (open V closed) [pr, =comm. Λ]

[2] open [1, =and4]

Now let’s try a more complex problem. You must only do one substitution at a time and identify what rules and propositions you used.

EX: Simplify the following using the proof format.

((open V closed) Λ malfunction) V true V open

Solution:

[pr] ((open V closed) Λ malfunction) V true V open

[1] (malfunction Λ (open V closed)) V true V open

[pr, =comm. Λ]

[2] (malfunction Λ open) V (malfunction Λ closed) V true V open [1, =distΛV]

[3] (malfunction Λ open) V (malfunction Λ closed) V

(true V open) [2, =rassocV]

[4] (malfunction Λ open) V (malfunction Λ closed) V (open V true) [3, =commV]

[5] (malfunction Λ open) V (malfunction Λ closed) V true [4, =or2]

[6] (malfunction Λ open) V true V (malfunction Λ closed) [5, =commV]

[6.5] (malfunction Λ open) V {true V (malfunction Λ closed) } [6, =rassocV]

[7] (malfunction Λ open) V {(true V malfunction) Λ (true V closed)} [6.5, =distVΛ]

[8] (malfunction Λ open) V {(malfunction V true) Λ (true V closed)} [7, =commV]

[9] (malfunction Λ open) V {true Λ (true V closed) } [8, =or2]

[10] (malfunction Λ open) V {true Λ (closed V true)} [9, =commV]

[11] (malfunction Λ open) V {true Λ true} [10, =or2]

[12] (malfunction Λ open) V true [11, =and2]

[13] true V (malfunction Λ open) [12, =commV]

[14] (true V open) Λ (true V malfunction) [13, distVΛ]

[15] (open V true) Λ (true V malfunction) [14,=commV]

[16] true Λ (true V malfunction) [15, =or2]

NOTE: Could have used [16,=and4] now and would be finished.

[17] true Λ (malfunction V true) [16,=commV]

[18] true Λ true [17, =or2]

[19] true [18, =and2]

Exercise3.4 6-10 answer.docx

Exercise 3.4

vi)

(O∧¬C) ∨ (O∧ C)

[(O∧¬C) ∨O] ∧ [(O∧¬C) ∨C] =dist∨∧

O∧ [(O∧¬C) ∨C] =or4

O∧ [(O∨C)∧(¬C ∨C)] =dist∨∧

O∧ [(O∨C)∧T ] =eximd

O∧ (O∨C) =and2

O =and4

vii)

(O \/ O) /\ (O \/ C) /\ O

O /\ (O \/ C) /\ O =or 1

O /\ O /\ (O \/ C) =comm /\

O /\ (O \/ C) =and 1

O =and 4

viii)

T \/ (O => C /\ M) \/ O

T =or 2

ix)

¬ ¬ ¬ M /\ ¬ ¬ ¬ ¬ O

¬ M /\ O (def neg)

¬ ¬ (M \/ O)

M \/ O (def neg)

Table of Contents.html

Frml Meth. Software E XLS Group CA Spring Semester 2018 CO - Week 5

1. Overview Module Five

2. USING RULES OF INFERENCE.doc

3. Truth Table for 3.4.doc

4. ProofTemplate

5. RULES+OF+INFERENCE

6. PROPOSITIONAL_CALCULUS_Section_3.4-2014

7. Exercise3.4 6-10 answer