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
0 answers

From Xor to Milp formula

In the most part of the text books on Mixed Integer Linear programming, one can find that $P_1$ XOR $P_2$ XOR ... XOR $P_n$ can be transposed in $p_1 + p_2 + ... + p_n = 1$ where each $p_i$ is a boolean variable associated to the propositions…
0
votes
2 answers

Why are these two simple statements equivalent?

As I study for my mathematical structures I final, I encountered a problem that I am unable to understand. The problem gives me the statement: If today is Tuesday, then we have class. I am being told that the statement that is logically equivalent…
0
votes
1 answer

How to Solve Disjunction Elimination Proof

How would you prove the following by disjunction elimination? Premises: A ∨ B , A ∨ C Conclusion: A ∨ (B ∧ C)
0
votes
1 answer

Identifying ambiguities

I used lead and deadly as the ambiguities because they both can have different meaning. But I'm not sure how to explain how they can have different meaning in this sentence and how to restructure this sentence to make it right. "Consider the…
Kifayat
  • 13
0
votes
2 answers

Image e and preimage of a set using logical connectors

This might appear silly, I know that $$ \begin{array}{l} f(A) = \left\{f(x) : x \in A \right\} \\ f^{-1}(A) = \left\{x : f(x) \in A \right\} \end{array} $$ If $y\in f(A)$ is fixed can this be expressed by the condition $$ \exists x, x\in A…
user8469759
  • 5,285
0
votes
1 answer

Proving associativity in propositional logic

$(p∧q) ∧ r ⊢ p ∧ (q∧r)$ In the sequent above, the only thing that happens is switching brackets between p&q and r, to q&r and separating out p. I could use the elimination rule between p&q and r, and get these separately, combine them with the…
0
votes
0 answers

Implication used in boolean condition

Sorry if this is a basic problem. Is the following true: $(p \rightarrow q) \land p \land r \vDash q \land r$? A little more detail, I am trying to determine the following: if $p \rightarrow q$ then is the follwing true: $p \land r \rightarrow q…
0
votes
1 answer

Finding disjunctive normal form (logic)

I have the following expression $(P\rightarrow Q) \wedge (Q\rightarrow R) \wedge (R \rightarrow P)$ and I want to create a DNF. I've gotten as far as getting rid of the implication, but I'm not sure how to get to the nice answer Wolfram Alpha gives…
Hiraphor
  • 179
0
votes
2 answers

Is it OK to insert a tautology in a proof out of thin air?

As far as I understand, normally all lines of a proof follow from some premises (except for the premises themselves, of course) or from lines following from premises, or from lines following from lines following from premises, .... But I have never…
0
votes
4 answers

Do we use the notation $p \vee q \wedge r$ without brackets?

Recently, one of my professors wrote $p \vee q\wedge r$. I'm not sure if it can be interpreted to either $p \vee ( q \wedge r)$ or $( p \vee q ) \wedge r$ or it is ambiguous. Please share your opinion. Anything is appreciated. Thank you.
ElementX
  • 922
0
votes
1 answer

what could be the answer of a compound proposition with 3 variables

I don't know how I could answer the truth table of $(p \lor q \lor ¬r) \land (p \lor ¬q \lor ¬s) $ because it's kind of confusing because it has 3 variables in one parentheses and I want some specific and clarified answer.
0
votes
0 answers

Logic-Deduction

I have: Lemma 1$$ \vdash\psi\rightarrow(\lnot\psi\rightarrow\varphi) $$ We also have $$ \{\lnot\varphi\rightarrow\varphi,\lnot\varphi\}\vdash\varphi $$ and $$ \{\lnot\varphi\rightarrow\varphi,\lnot\varphi\}\vdash\lnot\varphi $$ Can anyone explain…
0
votes
2 answers

What is the negation of each of the following statement?

Points R,S and T are collinear and T is not a point on the centered at R with radius RS Negation: Points R,S and T are not collinear and T is a point on the center at R with radius RS is this correct? Given a line l and a point P that is not on…
Maximiliano
  • 1,121
0
votes
1 answer

$\phi$ satisfies $\psi_1 \cup \psi_2$ then $\phi$ satisfies $\psi_1$ or $\phi$ satisfies $\psi_2$

The question was given to me in a recitation and the teacher assistant isn't available at the moment. The counter-example we were given was to define: $$\phi = p_1 \cup p_2$$ $$\psi_1 = p_1$$ $$\psi_2 = p_2$$ And then to look at $v_1$ $v_2$…
David
  • 71
  • 6
0
votes
1 answer

Converting a propositional logic formula to CNF (Conjunctive normal form)

I have a propositional formula that I have to convert to CNF and then write that in abreviated clausal form. I feel like i'm making a mistake somewhere but struggling to figure it out. Any idea what I am doing wrong here/what i'm missing? my…