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
1
vote
2 answers

How is this simplification done?

The models of the formula $p \rightarrow \neg(q \rightarrow r)$ are $V_{2}, V_{5}, V_{6}, V_{7}, V_{8}$. In disjunctive normal form this would be: $(p \wedge q \wedge \neg r) \vee (\neg p \wedge q \wedge r) \vee (\neg p \wedge q \wedge \neg r) \vee…
1
vote
3 answers

How to read parens

How do you read the parentheses in this proposition? That is, what do you say in English when reading from the end of a parenthesis to the next? Are the parens simply read as "such that"? $ ( ∀ x ∈ Z ) ( ∃ y ∈ Z ) x < y\\( ∃ y ∈ Z ) ( ∀ x ∈ Z ) x <…
1
vote
1 answer

Propisitional logic exam questions and answers

I'm going over exam questions, since my exam is hours away. I'd be extremely grateful if you could check out my answers and evaluate them. Hopefully you guys can see the truth table. Also, i have a question for one of you people who know this type…
1
vote
5 answers

Verify that $\bigl(p\to(q\to r)\bigr)\to \bigl((p\to q)\to (p\to r)\bigr)$ is a tautology.

Verify that $\bigl(p\to(q\to r)\bigr)\to \bigl((p\to q)\to (p\to r)\bigr)$ is a tautology. I am confused on this whole tautology even after looking at examples both in my book and on-line. I started a truth table and this is what I have so far.…
1
vote
1 answer

Translating from informal logical notation to formal logical notation

While introducing formal logical notation, the book I'm reading says the following: "$\forall x$ in $D$. $P(x)$" can be written as "$\forall x (x$ in $D \rightarrow P(x)$". "$\exists x$ in $D$ such that $P(x)$" can be written as "$\exists x(x$ in…
ankush981
  • 2,033
1
vote
1 answer

Validate or invalidate the propositional argument

Validate or invalidate the following arguments $ p\to t$ $ p \to \lnot r$ $q \to p$ $\lnot t \lor r$ $r \to t$ $\therefore \lnot p \land \lnot q \land (r \iff t) $ I could only see why it is $(r \iff t)$
LeonBrain
  • 159
  • 1
  • 6
1
vote
0 answers

Relationship between Propositional and First Order Logic

The language of Propositional Calculus comprises of the logical connectives and sentential symbols $A,B,C$ etc. The sentential letters can have arbitrary semantics and truth values. Two wff $\phi$ and $\psi$ can be 'independent' if there are truth…
Sudhir
  • 115
1
vote
3 answers

Stoll, Set Theory and Logic (pg 165): Logic for P->Q and P<->Q

Conditional P->Q: If P is True, then Q is also True. Truth table P Q P->Q T T T T F F F T T F F T BiConditional P<->Q: If P is True, then Q is also True; If Q is True, then P is also True. P Q P<->Q T T T T F F F T F F F T The motivation for the…
user101821
1
vote
3 answers

Duality discrete math problem

This is the only answer I got wrong on my HW and the prof does not want to give us the correct answers before our midterm The dual of a compound proposition that contains only the logical operators $\lor$ , $\land$ , and $\neg$ is the compound…
Kevin
  • 35
1
vote
3 answers

Solving logic word problems

So I have a number of statements of this "murder" word problem that I must solve. I will try and simplify them as much as possible. So I have these 4 different facts: If Sarah was drunk then either James is the murderer or Sarah lies Either James…
1
vote
2 answers

Relations in Propositional Logic

It is my understanding that relations are best described with predicate logic. I have a homework question that asks me to convert English sentences into propositional logic. The following list of sentences are similar to the homework, but do not…
Alex
  • 285
1
vote
2 answers

Truth Trees, Propositional Logic where conclusion is not related to premises

I have a problem that involves an argument in Propositional Logic. However, the conclusion has nothing to do with the premises (completely different variables). I'm fairly certain that this makes the argument invalid, since the conclusion does not…
Sinthet
  • 113
1
vote
1 answer

To translate truth table into English and decipher logical argument it makes

This is from How to prove it by Velleman. It will either rain or snow tomorrow. It is too warm to snow. Therefore, it will rain. Let P - It will rain tomorrow, Q - It will snow tomorrow; representing the argument symbolically, $P \vee Q$ $\neg…
Vikram
  • 5,580
1
vote
3 answers

Help on propositional calculus problem

Prove that the statements “$(p \mathbin{\text{and}} \neg q) \mathbin{\text{implies}} q$” and “$(p \mathbin{\text{and}} \neg q) \mathbin{\text{implies}} \neg p$” are logically equivalent. What simpler statement is logically equivalent to both of…
user87274
1
vote
1 answer

Removing redundancy in a propositional formula

I have the following propositional formula: $$\lnot A \land (\lnot A \lor \lnot B) \land (\lnot A \lor C) \land (\lnot B \lor C)$$ I can see and "explain" that the middle two terms in brackets are redundant, so the formula simplifies to: $$\lnot A…
Michael
  • 13