Symbolic Logic: Conditional/Indirect Proofs and Proving Theorems

Hey guys! So, this time, we’re going look at other methods we can use to construct proofs when just deriving from the premises isn’t enough.

Conditional Proof (CP)

The setup:

Basically, you use this method when the conclusion or a part of the conclusion you want is a conditional. This makes it so you assume the predicate in order to derive the consequent. Here’s an example:

Indirect Proof (IP)

The setup:

For this method, you use this primarily when the conclusion is a negated statement. You assume the un-negated form of the conclusion and attempt to find a contradiction so that the assumption is false, thus ending at the negated form. It also works the other way around where the conclusion isn’t negated so you make the assumption negated instead and then use the DN rule at the end. It’s also super useful when proving theorems where you have a limited plan of action. An example:

Theorems

Theorems are formulas that can be proven true without premises so the proofs for theorems have the additional challenge of not being able to build off of premises. Therefore, the above two methods are essential to be able to do proofs of theorems. Here’s an example:

RULES

  1. All assumptions must be discharged(closed).
  2. Lines between different assumptions must not cross.
  3. Once discharged, steps within the subproof cannot be used anymore.

On to the next page for a few practice problems!

Symbolic Logic: 10 Replacement Rules

This is part two of our little intro to Symbolic Logic. We’re going to expand our repertoire of rules we can employ in our proofs. These rules are all about putting logic statements into an alternative form. A lot of these rules will be familiar as they’re used in mathematics. One of the differences between these rules and the basic 8 is that these are reversible, hence the :: symbol to denote a two-way operation. The format of this post is going to be similar to the last one; the rules will be listed first, then some simple examples and then a couple of practice problems on the following pages.

1. Double Negation (D.N)

p :: ~~p

2. Commutation (Comm.)

p V q :: q V p

p • q :: q • p

3. Association (Assoc.)

[(p V (q V r)] :: [(p V q) V r)]

*applies to AND operators the same way*

4. Duplication (Dup.)

p :: p V p

5. DeMorgan’s Law (DeM.)

~(p V q) :: ~p • ~q

This law describes how a negation gets distributed into a parenthesised statement. It negates the two variables and switches the operator from an AND to an OR or vice versa. It only works on AND and OR operators though so if you have a (BI)CONDITIONAL operator inside the parenthesis, you’ll need to use one of the later replacement rules to make them into one.

6. Biconditional Exchange (B.E.)

(p ≡ q) :: [(p ⊃ q) • (q ⊃ p)]

7. Contraposition (Contra.)

(p ⊃ q) :: (~q ⊃ ~p)

8. Conditional Exchange (C.E.)

p ⊃ q :: (~p V q)

9. Exportation (Exp.)

[(p • q) ⊃ r] :: [(p ⊃ (q ⊃ r)]

10. Distribution (Dist.)

[p • (q V r)] :: (p • q) V (p • r)

[p V (q • r)] :: (p V q) • (p V r)


Examples




Alright y’all, on to the practice problems.

Symbolic Logic: 8 Basic Inference Rules

Hi y’all! So, if you’re computer science majors/philosophy major/etc., you probably have to take this class in college. I love this stuff because it’s very procedural and the proofs they give for you to solve are like puzzles and puzzles are super fun. Today, we’re gonna look at the 8 basic rules and then we’ll look at the replacement rules and more. I’m going to assume that y’all know the basic structure of sentential logic including operators and truth tables. Let’s get started.

Structure

A proof is a procedure which is supposed to derive the desired conclusion from a set of premises. To do this, the proof has to be set up in a certain way. First, all lines of a proof must be numbered. The premises make up the first lines of the proof along with the desired conclusion. Then, all subsequent derivations from the premises are listed below with the justification for each step listed along the right side, noting which rule was used and what lines of the proof were referenced. Here’s an example:

  1. Premise Pr. (for premise)
  2. Premise Pr. /:. Conclusion
  3. Derivation (Name of Rule) 1, 2 (lines 1 & 2 referenced)

For our purposes on this page, the visualisations for each of the rules below will not be written in this vertical fashion as they are cumbersome to format in the WordPress editor so it’ll be horizontal.

Let’s get into the rules and then work on some examples which will be on page 2.

1. Simplification (Simp.)

p • q /:. p

OR

p • q /:. q

If there is a conjunction, then both conjuncts can be individually represented as being true by themselves.

2. Conjunction (Conj.)

p; q /:. p • q

If two variables are true, then they can be joined in a conjunction.

3. Addition (Add.)

p /:. p V q

This rule is incredibly powerful as it allows you to introduce new elements into a disjunction as long as we have one of its disjuncts as true.

4. Disjunctive Syllogism (D.S.)

p V q; ~q /:.p

OR

p V q; ~p /:. q

If one of the disjuncts is stated to be false, then the remaining disjunct is true.

5. Modus Tollens (M.T)

p q; ~q /:. ~p

If the consequent of a conditional is false, then its antecedent is also false.

6. Modus Ponens (M.P.)

p q; p /:. q

If the antecedent of a conditional is true, then the consequent is also true.

7. Hypothetical Syllogism (H.S.)

p q; q r /:. p r

If the antecedent of a conditional leads to an antecedent of another conditional, then you can infer that the first antecedent leads to the consequent of the second conditional.

8. Rule of Dilemma/ Constructive Dilemma (C.D)

p V q; p s; q r /:. s V r

If either of the antecedents of two conditionals is true, then either of their consequents must also be true.


Alright, off to examples! We’re gonna start off easy and build onto harder and longer proofs.





Alright, now on to real problems; I have included two. I’ll give you guys the premises and the desired conclusion and I’ll post answers on how to derive the conclusion on the page after that. On to the next page!

How To Read/Trace Recursive Methods

So, recursion, one of the hardest units in APCS. The concept is pretty easy but the execution is a bit trickier. Today, I’m going to pass on a trick that my teacher taught me on how to trace your way through a recursion problem.

I’m going to assume that y’all already know what recursion is and how it works so I’ll jump straight into tracing. Let’s start off with a basic problem.

This problem is from here.

about-death

First, you have to start from the bottom of the page and go up from there. As you go through every iteration of the recursive statement, you make a new line. So, this method with an x = 5 and y = 2, if solved, would look like this:

Asch_experiment.svg

The bottommost line contains the original call to the method with 5 and 2 being x and y, respectively. The right of the diagram shows the operations within the recursive call and all the way at the top, the 17 represents what is returned by the base case when x becomes 0.

Let’s look at a recursive method that also prints something out in each iteration of the recursive statement.

This problem is from here.

about-death

For these problems, you would have to see where the print statement is in relation to the recursive statement. If the print statement is before the recursive statement, then the order of the printed lines go up and vice versa. So the tracing would look like this if n = 3:

about-death.png

So the output would look like:

3

2

1

Blastoff!

If the println statement was after the recursive statement, you would have to write them next to the after arrow and Blastoff! would be printed first.

So, these are the basics. If you guys have any specific questions for specific problems, feel free to contact me and I’ll help however I can.

This is Lieutenant out.

Commonly Missed Concepts of AP Macroeconomics

Alright, let’s review for AP Drawing Graphs and go over some of the most commonly missed (and least taught) concepts on the AP exam.

First off, C + I + G + NX = Y, which means consumption (by households aka the public) plus investment (by companies) plus gov’t spending plus net exports (which is exports minus imports) is equal to real GDP.

Crowding Out

Crowding out occurs when the government is deficit spending (or spending more than it’s making in revenue) and the government takes out loans to cover that extra spending. This phenomenon can be seen in the loanable funds market graph, which, in its original form, looks like this:

Loanable_funds_market
r is the interest rate, LF is the number of loanable funds available/offered

Since the government takes loans from the same supply of loans as the rest of us, deficit spending actually shifts the demand curve to the right and thus, reduces the number of loanable funds available to the rest of us and raises the interest level.

The resulting graph would look like this:

loanablefunds

*As a side note, government spending isn’t affected by the interest rate. While businesses and households (C and I) decrease spending when interest rates are higher (making it more expensive to take out loans), the government still has to spend what it has to spend so G isn’t affected by how high or low the interest rate on loans are.*

When the AP exam tests you on this, they won’t say straight out that the question is about crowding out so you’ll have to figure it out yourself. There are only usually one or two questions about crowding out though, so you’ll be fine.

Bond Prices

When a person buys gov’t bonds, they are basically buying gov’t debt. In exchange for buying the bond, they get a certain amount of money paid to them by the US gov’t as interest. What to keep in mind here is that interest rates and bond prices have an inverse relationship. When interest rates rise, previous bonds that were bought at a lower interest rate aren’t worth as much because you’re not getting as much money back with a bond that has a lower interest rate. The same is true of the reverse where lowering interest rates make the higher-interest bonds more valuable.

Quantity Theory of Money

The quantity theory of money states that MV = PQ: money supply times velocity of money is equal to the average price level times the number of goods/services produced. Basically, what this equation says is that there is a direct relationship between the money supply and how much things cost, which helps explain why Venezuela is experiencing massive inflation as the gov’t keeps pumping more currency into the system when there’s no real economic growth(and also why financing national debt doesn’t work).  Here’s an ACDC video that explains this concept:

Here’s the link to his channel. I promise his videos will be a huge help during the class. If you guys need help reviewing for AP Microeconomics, he has videos for that too.

 

Nominal vs Real Interest Rates

The thing to keep in mind about questions about nominal vs real interest rates is that the real interest rate doesn’t change because the banks won’t give up profit in order to offer lower interest loans so whatever effect inflation has on loans, it’s the nominal interest rates that will change to accommodate it.

For example, if the original nominal interest rate is 4% and inflation was 2% but is now 4%, the math would look like this:

Nominal = Real + Inflation

Originally: 4% = real + 2% so the real interest rate was 2%

After 2% increase in inflation:  nominal = 2% + 4% so the nominal interest rate would be 6% now.


That’s all I can think of for now. I’ll be uploading more AP Macro material on Outlet so if y’all need help with specific concepts, leave a comment or lemme know with the contact form. Remember to share the love and knowledge with your friends.

This is LtDemonLord and I’ll talk to y’all later.

AP Bio Cell Energetics Diagrams

Side Note: I don’t know if my little notes on the margins are entirely correct but the diagrams should be. If in doubt, always refer to your textbook or ask the teacher. This is one of the harder units along with genetics. Good luck!

APCS Chapter 6: 2D Arrays and ArrayLists

Alright, it’s time to tackle 2D arrays and arrayLists. 2D arrays are basically arrays of arrays. First off, 2D arrays:

2D Arrays

To start off with, the declaration and instantiation. Since 2D arrays are objects, we will use the new operator. There are several ways to do this:

The “normal” way:

data type [] [] name = new data type [# of rows] [# of collumns];

Example: I want to create a 2D array called nums containing int data with 2 rows and 3 collumns:

int[] [] nums = new int[2][3];

If you want to create a jagged array where each row is of a different length, then you can input your values directly into the 2D array. There are several ways to do this but I’m going to show you guys the simplest one:

int[] [] nums =

{

{4, 5, 6, 4},

{7, 234, 34, 1},

{23, 57, 2}

};

(Of course, you can write this all on one line but this layout looks more intuitive.)

So, this is what the 2D array would look like visually:

getimage

If this were a rectangular 2D array and not a jagged array, any attempt to retrieve a data value from the index position (3, 2) would return null so keep that in mind if you are manipulating or accessing a 2D array. There is also a thing called sparseArrays and an FRQ concerning sparseArrays has popped up on the AP exams (although I don’t think it’s likely to pop up again but hey, the more you know…) so here’s a link that kind of explains it but I don’t really think you need to know it for this class because it’s a little more high-level.

Traversing Through a 2D Array

With 2D arrays, you also need to know how to traverse through them. You can do this through the basic three types of loops. I’m going to show an example of each.

For Loops

You can use both the for loop and a for each loop. In my examples, I’m going to use the loops to add up all the numbers in the 2D array. I’m going to use the nums array that I instantiated above (all of the loops work with regular 2D arrays as well as jagged 2D arrays). This is how to use a regular nested for loop to go through every element in a 2D array and add them up.

int sum = 0;

for (int row = 0; row < nums.length; row++)

for (int col = 0; col < nums[row].length; col++)

sum += nums[row][col];

For Each Loop

For each loops are a little less intuitive to use but in the first part of the parameters denote which type of data type you’re trying to handle within the array and the second part is the array that you want to traverse through.

int sum = 0;

for (int[] num : nums)  //this looks at each row of thes 2D array

for (int i : num)  //this looks at all the data values within each row

sum+= num;

Both of these loops do the same thing.

While Loops

As a rule of thumb, while loops are used when you don’t know how many times iterations you need the loop to go through. I’m just going to use the basic example I used above and write a while loop instead.

int row = 0, col = 0, sum = 0;

while (row < nums.length) {

while (col < nums[row].length) {

sum += nums[row][col];

col++; }

row++; }

 ArrayLists

APCS Ch 6: Sorting and Searching Methods

Sorting methods as it pertains to arrays isn’t the simplest thing to wrap your head around but the concept and the way they should work should be pretty intuitive. You would need to know about two main sorting methods in APCS; the selection sort and the insertion sort. Like the different types of loops, both of these sorting methods have pros and cons attached to them.

Selection Sort

A selection sort is a tedious affair. Basically, what it does is takes each value in each index position and compares that value to all the other values to the right of it (after it) in the array. When it finds the smallest/largest value that exists to the right of its index position, it swaps places with it. In this way, this method sorts all of its value in either ascending or descending order of value.

Let’s take a look at what a selection sort in ascending order looks like in code:

//nums is an array of int values

//the variables min and minIndex both hold int values

for (int i = 0; i < nums.length – 1; i++)

{

min = nums[i];

minIndex = i;

for (int j = i; j < nums.length; j++)

{

if (nums[j] < min)

{

min = nums[j];

minIndex = j;

}

}

int temp = nums[i];

nums[i] = nums[minIndex];

nums[minIndex] = temp;

}

This is a daunting bit of code at first. However, if we understand mechanically how this sorting method works, it might help you understand better. For example, if I had an array of int values, this is what the array would look like after every pass of the outer loop:

cap

(1) The outer loop started at index position 0, took the number 16 at index 0 and started to loop through the values after it to find the smallest number, which happened to be the number 1 at index position 5. Then, the numbers 1 and 16 swapped places due to the inner loop. That was the first pass of the outer loop.

(2) Then, the outer loop looked at index position 1 and picked up the number 3 at index 1 and looped through the values to the right to find the smallest number. Since there were no values to the right that was smaller than 3, the inner loop swapped the 3 at index 1 with 3 at index 1, which meant the 3 swapped with itself and stayed where it is.

This process would repeat until it got to the second to last number by which time, the last number in the array would already be in its final sorted position so the number of passes the outer loop needs to fully sort an array is always the length of the array minus 1. By this rule, if we were on the fourth pass of the outer loop, the first four values of the array would have been in their final sorted places.

Let’s break down the code and see what the first pass of the outer loop looks like:

for (int i = 0; i < nums.length – 1; i++)

The outer loop just goes through the whole length of the array. In the first pass, i would be set to 0.

min = nums[i];

minIndex = i;

This sets min to the number currently at the index position of whatever element the outer loop is currently looking at. So, min would be set to the number at index 0 on the first pass, which would be the number 16. The index of the smallest number would be default set to the index of the number that we’re currently looking at, which would be index 0.

 for (int j = i; j < nums.length; j++)

This inner loop would loop through all the index positions to the right of the number at the index position we’re currently looking at, which would be all the values stored in the index positions after index 0.

if (nums[j] < min){

min = nums[j];

minIndex = j; }

This if statement compares the current min value (16) to all the values right of its index position (0). If it finds a number that is smaller, it will set the smaller value to min and set its index position to minIndex. The inner loop would cause this if statement to compare whatever smallest number it has found so far to the numbers in the index positions to the right. When it came to the number 1 at index 5, it set min to 1 and minIndex to 5. After going through the rest of the array, it didn’t find any smaller value so those variables stayed the same and we exit out of the inner loop.

int temp = nums[i];

nums[i] = nums[minIndex];

nums[minIndex] = temp;

This piece of code should look familiar; after all, it should be a simple puzzle that confronts many beginner programmers. Basically, what this does is it swaps the two numbers at the two index positions. In this case, temp would be set to 16, then the index position 1 would be overridden with the value at minIndex(5) which is 1. Then, temp (16) would override what was at index 5, effectively swapping the 16 and 1. This repeats until it has touched all but the last index position in the array, at which point the array is fully sorted and the outer loop terminates.

See next page for Insertion Sort

APCS Ch 6: Arrays Basics

Arrays are basically lists of things. This list can contain both objects and primitive data. The basic array can be declared and instantiated as such:

(data type)[ ] (arrayname) = new (data type) [(number of elements)];

Since arrays are considered as objects, the declaration and instantiation follow the pattern of other objects. So, if I wanted the array to store a total of ten names, I would make the array like so:

String[ ] names = new String[10];

Arrays have index values for every element they contain. If I had an array called nums that contained the numbers 1, 2, and 3, the number 1 would have the index position of 0, the number 2 would have index position 1 and the number 3 would have the index position 2 and so on.

Like Strings, arrays have a method that returns the length of the object. In the case of arrays, you would call the method .length. The  .length method for arrays does not need the double parentheses.

So, if you wanted to know the length (or number of elements) of the array names, you would do this:

names.length;

We now go on to loops. This is quite simple. Looping through an array is pretty easy and intuitive. If I were to use a for loop to go through every element of the array names which contains 10 String objects, it would look something like this:

for (int i = 0; i < names.length; i++)

{

//body of the loop

}

AP Com Sci Chapter 2 Lab Review

Heya! This will be the first of the AP Com Sci lab solutions on Outlet. I will be uploading these labs starting from Chapter 2 because Chapter 1 is a no-brainer. For that matter, Chapter 2 is a no-brainer too. I will upload parts of the code because even though these posts are supposed to contain the “answers”,  you’re still going to have to know how to write these programs and know the concepts behind the programs to pass this class. I will not contribute to your failure. If you have any questions, you can comment them below or shoot me an email on the contact page.

For Chapter 2, I will only post about three labs, the Base Conversion Lab (pg 2-4), the Circle Labs (of which I’ll cover the Circle2 part on pg 5-7) and the String Manipulation Lab (pg 8-10) since the rest are the most fundamental basics and don’t have much to cover.

Let’s get right into it.