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
3
votes
1 answer

How to prove soundness of propositional logic

For any proposition $φ$ and any set of propositions $Γ$, if $Γ⊢φ$, then $Γ⊨φ$. I find the same question here. However, we don't have the definition of formula and axiom yet. This is the hint given on the slide: The proof of the Soundness Theorem…
yashirq
  • 505
3
votes
1 answer

Different propositional logics in Sodoku

I have started reading Rosen's Discrete Mathematics and I have reached the topic of propositional satisfiability and it's application in solving Sudoku. Solving such puzzles consists of solving the following assertions: Every row contains every…
3
votes
1 answer

Truth of propositional formula (dependence on variable)

Identify the correct statements about $2^n\ge100$. The choices are: This is a proposition This is not a proposition Its truth value depends on the value of $n$ Its truth value depends on the value of $2^n$ I know this is not a…
yroc
  • 1,075
3
votes
2 answers

How to interpret square brackets and valuations in propositional logic?

I am faced with this task: "Let M be the set of all valuations. Let for each propositional formula $A: [A] = v \in M : v(A) = 1$. Show that: $[A \land B] = [A] \cap [B]$ So, I get the idea what I'm supposed to prove, but the definitions escape me. I…
2
votes
1 answer

Propositional logic and distributive law

I am having trouble trying to understand how this question passes from this point $$ ( ( p\vee q )\wedge (p \vee \neg r ) \wedge (\neg q \vee \neg r ) ) \vee ( \neg p \vee r ) $$ to this $$ (p\vee q \vee \neg p \vee r)\wedge(p \vee \neg r \vee…
2
votes
1 answer

Propositional Calculus - Validity Question

I have the following question: And I have drawn up the truth table below: My question is I see there is one truth value that both the premise and conclusion have in common, but does that mean that the premise does or does not entail the…
2
votes
6 answers

(Homework) Prove the law of syllogism

Trying to prove, by symbol manipulation, that if $(P \rightarrow Q) \wedge (Q \rightarrow R) \rightarrow (P \rightarrow R)$ I am stuck after doing these steps: (P $\rightarrow Q) \wedge (Q \rightarrow R) \rightarrow (P \rightarrow R$) $(\neg P \vee…
nx__
  • 341
2
votes
4 answers

Indirect proof , odd and even numbers

"Show by indirect proof that if 5n + 3 is an even number then n is an odd number" How could this be solved? I guess I'm in the right track but I don't know how to conclude.
user170421
2
votes
1 answer

Relation between an unsatisfiable set and a tautology

In mathematical logic, satisfiability and validity are elementary concepts of semantics. A formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true. A formula is valid if all interpretations make the…
user166355
2
votes
1 answer

How does the propositional logic of the following IFF proof (DAGs and topological ordering) work?

I was reading the following proof and am having trouble following the propositional logic underpinning the proof: http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Graph/DAG.html To simplify, it looks to me like the propositional logic is as…
2
votes
1 answer

Propositonal equivalence and compound proposition

Without using truth tables, show that the statements ‘If you did all problems in the book, attended all lectures and completed all assignments, then you will get an A in Discrete Math’ and ‘If you did all assignments but did not get an A in…
2
votes
1 answer

Confusion in Conjunctive normal forms

Which of the Following is TRUE about formulae in Conjunctive Normal form? For any formula, there is a truth assignment for which at least half the clauses evaluate true. For any formula, there is a truth assignment for a which all the clauses…
2
votes
1 answer

Propositional logic truth tables

For the exam that I am taking, propositional always comes up with identical questions. These include writing a sentences in propositional logic, which I can do. But also drawing a truth table for propositional logic, which I can't do. I find It…
user119325
  • 127
  • 1
  • 6
2
votes
1 answer

Help understand "unless"

The statement "r unless s" is defined as "if $\sim s$ then $r$." Now, I can proceed as follows: $$\sim s \rightarrow r $$ $$\equiv \; \sim (\sim s) \vee r$$ $$\equiv \; s \vee r$$ Which means that when $s$ and $r$ both are true, the statement is…
ankush981
  • 2,033
2
votes
0 answers

Help with propositional logic

Hi all this is for a homework where we just started learning logic and I am not very familiar with propositional logic. So we have two problems: To show a proof of the Sherlock Holmes syllogism using Quine's method My solution is: The syllogism is…
1 2
3
30 31