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).
5,653 questions
-2
votes
0
answers
55
views
What semantic implications do contradictions have in set definitions? [closed]
I’m trying to put “$A \setminus B = A \triangle (A \cap B)$” in terms of predicates and connectives. If $A$ and $B$ are subsets of a set $U$, and taking into account that $A \setminus B = \{x \in U \...
- 31
0
votes
1
answer
38
views
How to find the number of valid schedules after expressing the four logical conditions?
I’m working on a logic and combinatorics problem about arranging a teacher’s Monday schedule.
The schedule has four sessions (1, 2, 3, 4) and four subjects: Mathematics (M), Biology (B), Geography (G),...
-1
votes
0
answers
34
views
How to solve this problem? I just write the proposition from the 4 premise and don't know the solution that followed in style of logic [closed]
Using propositional logic to solve the following problem:
A teacher wants to arrange a teaching schedule for Monday morning. This schedule must satisfy the following four conditions:
Mathematics ...
1
vote
1
answer
95
views
In propositional logic, what is the distinction between the material implication/conditional and Reductio Ad Absurdum? [closed]
In propositional logic: isn't the RAAD equivalent to what the definition of the material conditional implies? As in the material conditional both Q = 0 and Q = 1 signifiy a true formula when the ...
- 31
0
votes
0
answers
79
views
How does the truth table for logical IF work for the statement "$n$ is even" and "$n$ is divisible by 2"? [duplicate]
The truth table of the IF operator is shown in the above.
Let p be "a number $n$ is even" and q be "a number $n$ is divisible by 2"
Then If p then q evaluates to true if both ...
- 8,661
2
votes
0
answers
52
views
How to prove that this is a valid NAND proof system? [duplicate]
I was playing the excellent math game "The Incredible Proof Machine", which is a tutorial of sorts on formal proofs using a block-based, flowchart-style system of logical inferences. One of ...
- 21
1
vote
1
answer
128
views
Translating "Someone has visited every country in the world except Libya"
Let $V(p, c)$ mean that person $p$ has visited country $c$ in the world.
Is the following deconstruction correct?
Someone has visited every country in the world except Libya.
There is a person $p$ ...
- 27.8k
1
vote
1
answer
120
views
Is Negation Laws same as Law of Excluded Middle?
Negation Laws shown in Table-6 here are stated as:
$$p ∨ ¬p ≡ \mathbf{T} \text{ and } p ∧ ¬p ≡ \mathbf{F}$$
Is it same as the Law of Excluded Middle? This gets confusing for a novice like me when same ...
- 119
4
votes
2
answers
156
views
Formally prove that $\phi\rightarrow \psi \vdash \neg \psi \rightarrow\neg \phi$ in Hilbert system
In the book Gödel's Theorems and Zermelo's Axioms by Halbeisen and Krapf the first chapter contains an excercise that asks us to prove
$$\phi\rightarrow \psi \vdash \neg \psi \rightarrow\neg \phi,$$
i....
- 173
4
votes
1
answer
88
views
Expressive adequacy of $\{ \text{IFTHENELSE},\, \bot,\, \top \}$ - What is the correct truth table? [closed]
I recently took an introductory logic course (I am a philosophy student) and on the final exam one of the questions asked me to draw up a truth-table for $( ( \alpha \to \beta ) \wedge ( \neg \alpha \...
- 49
0
votes
1
answer
86
views
Prove using Hilbert system that $A,\lnot B \vdash \lnot (A \land B)$
I'm reading A Course in Mathematical logic and Computability Theory by Gerasimov and for the exercise the book asks the question to prove the following statement in Hilbert proof system:
$$A,\lnot B \...
- 383
3
votes
1
answer
179
views
What is a theory?
I'm trying to learn category theory and in my adventures reading Borceux's "Handbook of Categorical Algebra 2", I encountered the following definition:
A presentation of an algebraic theory ...
- 992
2
votes
2
answers
201
views
Proving $(A\to B)\to\perp$ $\Rightarrow$ $A\land(B\to\perp)$ within 10 steps(12 "blocks")
The last task in Session 5 of the Incredible Proof Machine(a tool to perform proofs in various logics visually) is to prove $A\land(B\to\perp)$ when given $(A\to B)\to\perp$, in which capitals ...
- 594
1
vote
0
answers
48
views
Proving the functional completeness of a set of non-2-value binary logical operators
While it's relatively easy to look up how to prove that a set of 2-value logical connectives is functionally complete (e.g. via Post's formalisation or other methods; there's a decent enough Wiki page ...
- 11
4
votes
2
answers
125
views
How to Substitute a term for a bound variable in a quantified formula of first order logic?
I am currently working through the textbook An Introduction to Mathematical Logic and Type Theory: to Truth through Proof, by Peter Andrews, and there have been occasions where I've felt like Andrews ...
- 527