Questions tagged [propositional-calculus]

Appropriate for questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions. Also for general questions about the propositional calculus itself, including its semantics and proof theory. Questions about other kinds of logic should use a different tag, such as (logic), (predicate-logic), or (first-order-logic).

Propositional logic is a branch of logic dealing with logical connectives and statements involving them. A logical connective connects finitely many sentences and forms a compound sentence, in a way that the truth value of the compound sentence depends only on the truth value of its constituents. The most common connectives are the binary connectives conjunction ($\land$), disjunction ($\lor$) and implication ($\rightarrow$), the unary connective negation ($\neg$), and the nullary connectives true ($\top$) and false ($\bot$).

Any proposition is considered to be either atomic (in which case it has no constituents) or compound (in which case it's formed by mean a connective using simpler propositions). A propositional model is a function assigning to each atomic proposition a truth value $0$ or $1$. The truth values of compound propositions are then determined by the truth values of their constituents. For example, if $I$ is a function assigning truth values to propositions, one would have $I(\top)=1$, $I(\bot)=0$, $I(\neg A)=1-I(A)$, $I(A\land B)=\min\big(I(A),I(B)\big)$, $I(A\lor B)=\max\big(I(A),I(B)\big)$ and $I(A\rightarrow B)=\max\big(1-I(A),I(B)\big)$. The propositions having the value $1$ for every model, are called tautologies, and those having the value $0$ for every model, are called absurdities. A central task of propositional logic is characterizing tautologies and absurdities.

5541 questions
0
votes
3 answers

Logical Equivalence of two propositions

Are the following two propositions logically equivalent? $p \rightarrow (\neg q \land r)$ and $\neg p \lor \neg(r \rightarrow q) $ For this one, I'm pretty sure that they are not equivalent because of DeMorgan laws, but I'm not sure how to prove…
CSstudent
  • 249
  • 2
  • 15
0
votes
1 answer

Proving the negation of conditional via propositional calculus

https://www.dropbox.com/s/2dpk7fvae668phn/Screenshot%202016-03-03%2018.13.42.png?dl=0 Hi, I'm trying to prove the negation of a conditional. Basically, prove ¬(α → b) is equivalent to α ∧ ¬b. I've figured out to prove ¬b, but I can't seem to get a…
0
votes
1 answer

How to specify the corresponding line of a truth table in a formula?

How to specify the corresponding line of a truth table in a formula: $$p \to (\neg q \lor (q \to p))$$ $p$ evaluates to $F$ and $q$ evaluates to $T$. I want to know the method followed to find this.
0
votes
2 answers

Is the following statement equivalent?

Is the following statement equivalent: $((A \vee \neg C) \wedge ((\neg B) \leftarrow C)) \vee \neg (A \wedge B) \equiv (\neg A \vee \neg B \vee \neg C) $ Our prof gave us an exercise with this statement and said we should simplify it with truth…
fragant
  • 406
0
votes
1 answer

Valid Arguments

If i have the following arguments : \begin{align} & a \to (b \lor c)\\ & \lnot b \lor \lnot c \\ & c \lor a \\ & --- \\ & b \end{align} How do i prove that its valid. My thought was that if the conclusion is false, that is to say b = F, and…
0
votes
3 answers

Prove [(q ˄ (p ↔ ¬ q) ) → q] is a tautology using logic laws

How to prove that this statement is tautology using logic laws (q ˄ (p ↔ ¬ q) ) → q Edit: I got stuck here after trying to apply De Morgan's law: (q ˄ (p ↔ ¬ q)) → q ¬ [q ˄ (p ↔ ¬ q)] ˅ q ¬ q ˅ ¬ (p ↔ ¬ q) ˅ q ¬ q ˅ (¬ p ↔ q) ˅ q ¬ q ˅ [(¬ p → q) ˄…
0
votes
2 answers

(Propositional logic): Can I do a conjunction in the antecedent of a conditional

Can I do a conjunction in the antecedent of a conditional? i.e. step 7 in my derivation below legit? $A \rightarrow B\qquad\qquad$ (Premise) $A \rightarrow C\qquad\qquad$ (Premise) $A \phantom{{}\rightarrow C}\qquad\quad\quad$ (Premise) $B…
Wei
  • 23
0
votes
2 answers

Is it possible for there to be a mechanical way in which one would prove a tautology (in a propositional calculus)

Basically is there any algorithm for proving a tautology? (even if it runs in exponential time?) Additionally, is it possible for a propositional calculus to be such that a tautology is presented in a way in which it is clear that it is a tautology…
0
votes
1 answer

Is this simplification of boolean algebra correct?

CW = A`.B.C`.D` + A.B`.C`.D` + A.B`.C.D` + A.B.C`.D + A.B.C.D` CW = A`.B.C`.D` + A.B`.D`(C`+C) + A.B(C`.D + C.D`) CW = A`.B.C`.D` + A.B`.D`(1) + A.B(C`.D +D`.C) CW = A`.B.C`.D` + A.B`.D` + A.B(C`.1.C) CW = A`.B.C`.D` + A.B`.D` + A.B(1) CW =…
0
votes
0 answers

Find truth value of propositional function

I have this propositional function: $p(x,y):y-x=y+x^2$ and I have to find truth value for: $\forall{x}\exists{y}$ $p(x,y)$ $\exists{y}\forall{x}$ $p(x,y)$ Set of all numbers is integer numbers $Z$. I am not sure if this is the same or not. My…
Johny
  • 225
0
votes
2 answers

how to represent some sentences in propositional logic

HI does anyone know how to convert these two statements into propositional logic,?? 1."Any person can fool some of the people all of the time,all of the people some of the time,but not all of the people all of the time" 2."peter has at least two…
Monika
  • 9
0
votes
0 answers

How to derive this equivalence in propositional logic (Xv!X)->(X->Z)v(Z->X)

I have no special skills of doing this. Can you introduce how to think of that ? I could take Xv!X as hip and then proof by parts x -> (X->Z)v(Z->X). But is the best way always to split disjunction ? Maybe some kind of simple learning resources…
Timotei
  • 21
0
votes
1 answer

Rule of inference proof

"Either I go to library or if I wait for my mom then I have to go to the party." "I will go to the party if I meet my friends" "If I go to the library then I will finish my homework." "I did not finish my homework." Use the rule of inference to…
0
votes
1 answer

Big notation Propositional Formulas

I am reading a lecture and there is a sentece that say: Every tautology $\tau$ on $n$ variables has an proof in which there are at most $2^{O(n)}$ formulas. I know that $O$ is the big notation used for the worst case in algorithms, but in this…
user46060
0
votes
1 answer

If $Γ,A \vDash B$ and $Γ,A \vDash \lnot B$, then $Γ \vDash \lnot A$

The task is to show that for every set Γ of propositions: If $Γ,A \vDash B$ and $Γ,A \vDash \lnot B$, then $Γ \vDash \lnot A$. This follows Gallier's notation and is actually taken right out of his book. However, I have trouble showing this. I…
Marcel
  • 129